Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.98/48: Рейтинг темы: голосов - 48, средняя оценка - 4.98
DmitriiS
1

Реализация Китайской теоремы об остатках

18.11.2013, 22:56. Показов 9298. Ответов 1
Метки нет (Все метки)

Задача программы - найти X, исходя из трёх сравнений.
Код я написал, но никак не пойму, почему X принимает отрицательное, да и неправильное значение.
Проверьте, пожалуйста, если кому не лень)

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
 
//Функция для вычисления НОД - проверка взаимно простых
unsigned int gcd(unsigned int a, unsigned int b)
{
    while (a && b)
        if (a >= b)
           a = a % b;
        else
           b = b % a;
    return a | b;
}
 
//Функция Эйлера
int euler(int n)
{
    int ans;
    ans = n;
    for (int i = 2; i*i <= n; i++)
        if (n % i == 0)
        {
            while (n % i == 0) n = n/i;
            ans = ans - ans / i;
        }
    if (n > 1) ans = ans - ans / n;
    return ans;
}
 
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    //x = a(mod m)
    int A, i, j, k, c, X;
    setlocale(LC_ALL, "Russian");
 
    //снимем нужные данные с клавиатуры
    cout << "Вы имеете систему уравнений вида:" << endl << "x = a[1] (mod m[1])" << endl << 
        "x = a[2] (mod m[2])" << endl << "..............." << endl << "x = a[k] (mod m[k])" << endl << "где i = 1, 2, ..., k." << endl;
    cout << "Программа создана для того, чтобы реализовывать Китайскую теорему об остатках," << endl << " т.е. находить число X по остаткам от деления на взаимно простые числа." << endl <<
        "Введите сначала число k - количество уравнений системы." << endl;
    cin >> k;
    if (cin.fail())
        do
        {
            cout << "---Error!---" << "Введите число!" << endl;
            cin.clear();
            cin.sync();
            cin >> k;
        }
        while (cin.fail());
 
    int *m = new int[k];
    int *a = new int[k];
    int *N = new int[k];
    int *M = new int[k];
    int *f = new int[k];
    memset(m, 0, sizeof(m));
    memset(a, 0, sizeof(a));
    memset(N, 0, sizeof(N));
    memset(M, 0, sizeof(M));
    memset(f, 0, sizeof(f));
 
    retry : ;//при ошибке возврат сюда
    for (int i=0; i<k; i++)//a[i] и m[i]
    {
        cout << "Введите числа m[" << i + 1 << "] и a[" << i + 1 << "] через пробел соответственно." << endl;
        cin >> m[i];
        if (cin.fail())
            do
            {
                cout << "---Error!---" << "Введите число!" << endl;
                cin.clear();
                cin.sync();
                cin >> m[i];
            }
            while (cin.fail());
 
        cin >> a[i];
        if (a[i] > m[i])
            do
            {
                cout << "a[i] должно быть меньше m[i]" << endl;
                cin.clear();
                cin.sync();
                cin >> a[i];
                if (cin.fail())
                    do
                    {
                        cout << "---Error!---" << "Введите число!" << endl;
                        cin.clear();
                        cin.sync();
                        cin >> a[i];
                    }
                    while (cin.fail());
            }
            while (a[i] > m[i]);
    }
 
    //проверим, взаимно ли просты элементы массива m
    for (int i=0; i < k; i++)
        for (int j=0; j < k; j++)
            if ((i != j) && (gcd(m[i], m[j]) != 1))
            {
                cout << "m[i] должны быть взаимно просты! Возврат к вводу m[i] и a[i]." << endl;
                goto retry;
            }
 
    //приступим, наконец к нахождению X
    A = 1;
    for (int i=0; i < k; i++)
        A = A * m[i];
    for (int i=0; i < k; i++)
        M[i] = A / m[i];
 
    for (int i=0; i < k; i++)
    {
        f[i] = euler(m[i]);
        //N[i] = exp(M[i] * log(f[i] - 1.0));
        c = N[i];
        for (int j=1; j <= f[i] - 1; j++)
            N[i] = N[i] * c;
        N[i] = N[i] % m[i];
    }
 
    //само значение X
    X = 0;
    for (int i=0; i < k; i++)
        X = X + a[i] * N[i] * M[i];
    
    cout << "Решение системы сравнений" << endl;
    for (int i=0; i < k; i++)
        cout << "X = " << a[i] << "(mod" << m[i] << ")" << endl;
    cout << "имеет вид:" << endl << "X = " << X << "(mod" << A << ")" << endl;
 
    delete[] m;
    delete[] a;
    delete[] N;
    delete[] M;
    delete[] f;
    system("pause");
    return 0;
}

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.11.2013, 22:56
Ответы с готовыми решениями:

Код Китайской теоремы остатков
Доброго времени суток. Помогите, пожалуйста. В учебнике Б.Штайера &quot;Прикладная криптография&quot;...

Реализация Теоремы Штурма
Необходимо написать программу для нахождения количества действительных корней многочлена n-й...

Схема разделения секрета на основе китайской теоремы об остатках. Литература
Здравствуйте. Подскажите пожалуйста, что почитать попроще на эту тему. Уже наткнулся на статью в...

Найти решение системы сравнений по китайской теореме об остатках
Здравствуйте! Решаю одну задачу, где нужно в кольце целых чисел найти x из системы сравнений по...

1
Belfegor
18.11.2013, 22:59     Реализация Китайской теоремы об остатках
  #2

Не по теме:

увидел метку, понял что goto, пошел дальше%-)

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.11.2013, 22:59

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Доказательство гипотезы (теоремы) Эндрю Била в контексте "Полного доказательства великой теоремы Ферма методом деления"
УДК 512.1 Доказательство гипотезы Эндрю Била Ведерников Сергей Иванович –...

Теорема об остатках
завтра сдать надо((

Китайская теорема об остатках
когда коэфф взаимно простые, решение понятно но вот , например 2x =1mod(4) 4x=1(mod2) без...

Китайская теорема об остатках
товарищи есть у кого-то исходный код на Си который реализует данную теорему или может знаете где...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.