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

@Vitosha_Z · Регистрация: 11.01.2017

Author24 — интернет-сервис помощи студентам

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

C++

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), а здесь только два. Подскажите, что означают эти два параметра и где третий?

@Haklag · 14.02.2017, 09:26

Функция modexp – это экспонента по модулю, то есть число е в степени деленное по модулю, поэтому base здесь передавать не нужно – он всегда е.

@Vitosha_Z · 14.02.2017, 12:08 **[ТС]**

Подскажите еще, пожалуйста, в книге Б.Штайера сказано:
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}. Верно ли я понимаю?

@grizlik78 · 14.02.2017, 15:08

Сообщение от 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])

@Haklag 34 / 34 / 37 Регистрация: 21.06.2012 Сообщений: 152
	14.02.2017, 09:26	2
	Функция modexp – это экспонента по модулю, то есть число е в степени деленное по модулю, поэтому base здесь передавать не нужно – он всегда е. 1

@Vitosha_Z 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

	14.02.2017, 15:08