Дипломная работа: Математические основы системы остаточных классов

Вход : Пары , такие, что , , где каждое > 1 и (,) = 1 для и - короткие целые числа.

Выход : х – единственное наименьшее неотрицательное решение системы по модулю .

1. Инициализация. Р :=1; х :=МОД(,) – подпрограмма нахождения остатка деления на .

2. Цикл для i от 1 до n – 1: MOДINV(p , );

q :=МОД(

3. х := х + pq , где MOДINV – подпрограмма вычисления мультипликативного обратного элемента.

4. q :=МОД(

5. Вернуть х .

Несложный анализ времени работы данного алгоритма показывает, что

где - количество цифр числа Р , т. е. длина числа Р , при этом функция L ведёт себя как логарифм.

§ 4. Теоремы Эйлера и Ферма, их роль в вычислении мультипликативных обратных элементов по данному модулю

Вернёмся теперь к вопросу о мультипликативных обратных элементах в фактор-кольце Z_p .

Теорема . Пусть , тогда класс имеет мультипликативный обратный элемент по модулю р тогда и только тогда, когда (, р ) = 1.

Теорема . Характеристика λ конечного поля – простое число.

Рассмотрим два способа вычисления обратных мультипликативных элементов. Первый способ основан на рассмотренном выше алгоритме Евклида, второй – на теореме Эйлера.

Первый способ . Из условия (а , р ) = 1 получаем ах + ру = 1 или и, следовательно, х – мультипликативный обратный к а по модулю р .

Второй способ . Предварительно напомним теорему Эйлера:

(а , р ) = 1, доказательство которой достаточно простое и мы его не приводим, так как его можно найти в любой книге по теории чисел. Частным случаем теоремы Эйлера является малая теорема Ферма.

Малая теорема Ферма . Если р – простое число и а – произвольное целое число, не делящееся на р , то .

Следствие . В кольце Z_p классов вычетов по модулю р из следует, что

Таким образом, для вычисления мультипликативного обратного к классу по модулю р в случае, когда , достаточно возвести в степень k , где k = р – 2, если р – простое число, и в противном случае.

Ясно, что при таком методе вычисления мультипликативного обратного элемента задача сводится к цепочке умножений и делений с остатком на модуль р . Эта задача решается без особых трудностей, если наименьший положительный вычет , где , представлен в СОК. Однако возникает вопрос об эффективности этого метода. Другими словами, является ли наименьшим показателем степени, для которого ? Оказывается, что нет.

Из китайской теореме об остатках следует следующее

Утверждение . Пусть - каноническое представление числа р . Тогда функция, которая каждому классу ставит в соответствие кортеж , где для , является кольцевым изоморфизмом кольца класса вычетов по модулю р и кольца кортежей вида , где для . Более того, если обозначить через * любую из кольцевых операций + или · , то

Таким образом,

,

т. е. кольцо классов вычетов по модулю р раскладывается в прямое произведение колец классов вычетов по модулям . Это разложение колец индуцирует разложение групп их обратимых элементов:

.