0 / 0 / 0
Регистрация: 11.01.2017
Сообщений: 2
1

Код Китайской теоремы остатков

14.02.2017, 00:46. Показов 3903. Ответов 3
Метки нет (Все метки)

Доброго времени суток. Помогите, пожалуйста. В учебнике Б.Штайера "Прикладная криптография" описывается код Китайской теоремы остатков на языке Си:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Chinese_remainder(size_t r, int *m, int *u)
        {
            size_t i;
            int modulus;
            int n;
            modulus = 1;
            for (i = 0; i < r; ++i)
                modulus *= m[i];
            n = 0;
            for (i = 0; i < r; ++i)
            {
                n += u[i] * modexp(modulus/m[i] * totient(m[i]), m[i]);
                n %= modulus;
            }
            return n;
        }
Функция modexp я так понимаю, это возведение в степень по модулю. Но modexp принимает 3 параметра (base, exponent, modulus), а здесь только два. Подскажите, что означают эти два параметра и где третий?
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.02.2017, 00:46
Ответы с готовыми решениями:

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

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

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

Выяснить, правда ли, что сумма остатков от деления нечётных x на k будет больше чем сумма остатков от деления чётных x на k
Ввести N чисел: 1 2 , ,..., N x x x , (N ≥3) и число k . Выяснить, правда ли, что сумма остатков ...

3
34 / 34 / 37
Регистрация: 21.06.2012
Сообщений: 152
14.02.2017, 09:26 2
Функция modexp – это экспонента по модулю, то есть число е в степени деленное по модулю, поэтому base здесь передавать не нужно – он всегда е.
1
0 / 0 / 0
Регистрация: 11.01.2017
Сообщений: 2
14.02.2017, 12:08  [ТС] 3
Подскажите еще, пожалуйста, в книге Б.Штайера сказано:
m - это массив (попарно взаимно простых) модулей;
u -это массив коэффициентов возвращает значение n, такое что n==u[k]%m[k] (k=0..r-1)
Если 14 mod 3 = 2 и 14 mod 5 =4, то чтобы найти это число 14 по простым числам и остаткам,
массивы m[i] и u[i] должны быть равны m[]={3, 5}, a u[]={2, 4}. Верно ли я понимаю?
0
Эксперт С++
2361 / 1649 / 275
Регистрация: 29.05.2011
Сообщений: 3,378
14.02.2017, 15:08 4
Цитата Сообщение от Haklag Посмотреть сообщение
Функция modexp – это экспонента по модулю, то есть число е в степени деленное по модулю, поэтому base здесь передавать не нужно – он всегда е.
Это не так. Основание должно быть целым числом.
Цитата Сообщение от Vitosha_Z Посмотреть сообщение
Но modexp принимает 3 параметра (base, exponent, modulus), а здесь только два.
Здесь опечатка. В бумажной версии вызов выглядит так:
C++
1
n += u[i] * modexp(modulus/m[i], totient(m[i]), m[i]);
Первый параметр — основание, второй — степень, третий — модуль.
Только это всё-равно не должно работать правильно.
Дело в том, что если это возведение в степень по модулю (а это скорее всего так и есть), то modexp(modulus/m[i], totient(m[i]), m[i]) в виде формулы записывается так:
https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(\frac{M}{m_i}\right)^{\varphi(m_i)} \mathrm{mod} \, m_i
что по теореме Эйлера всегда даёт единицу.

Добавлено через 2 минуты
Скорее всего правильное выражение должно выглядеть так:
C++
1
n += u[i] * modulus/m[i] * modexp(modulus/m[i], totient(m[i])-1, m[i])
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.02.2017, 15:08

Верно ли, что сумма остатков от деления нечётных x на k будет больше, чем сумма остатков от деления чётных x на k
Ввести N чисел :х1,х2,..хn (N&gt;=3) и число k.Выяснить, правда ли, что сумма остатков от деления...

Общение с китайской штуковиной
Доброго времени суток. Заказал себе двух частотный rfid reader/writer Но так как я сом по себе...

Планшеты страны китайской
Смотрю в сторону китайских планшетов. Очень интересуют эти устройства, но интересуют следующие...

Хотелось бы избавиться от китайской байды
И от другого мусора, который есть

Как модифицировать прошивку китайской видекарты
Здравствуйте. На днях друг притянул мне видюху gtx 1050 ti. Сказал что купил у китайцев, на &quot;али&quot;....

Как питается контроллер в китайской гирлянде?
Привет! Мучаюсь уже второй Новый год, решил спросить. :) Нашел тут схему китайской гирлянды:...


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

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

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