Математические основы системы остаточных классов (стр. 4 из 19)

Вход: Пары

, такие, что , , где каждое > 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, если р – простое число, и в противном случае.

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

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

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

Утверждение. Пусть

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

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

,

т. е. кольцо классов вычетов по модулю р раскладывается в прямое произведение колец классов вычетов по модулям

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

.

Можно сделать вывод о том, что произвольное целое положительное число А, 0 < A < P, где

и для , однозначно представимо своими наименьшими неотрицательными остатками по модулю , причём сложение (а, следовательно, и вычитание) и умножение выполняются покомпонентно.

Как следует из китайской теоремы об остатках, можно использовать любой соответствующий интервал

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

§ 5. Числа Мерсенна, Ферма и операции над ними

При рассмотрении отдельных классов простых чисел значительный интерес представляет вопрос о простых числах вида

, где m – нечётное, именуемые числами Мерсенна. При простых значениях m = p число может оказаться простым, но может быть составным.

Например, при р = 2, 3, 5, 7, 13, 17, 19 мы получаем простые числа Мерсенна: 3, 7, 31, 127, 8191, 131071, а при р = 11, 23, 29 числа

- составные.

Числа вида

, где k – положительное, обычно называют числами Ферма. При k = 0, 1, 2, 3, 4 числа Ферма простые: 3, 5, 17, 257, 65537. Все остальные числа Ферма – составные. Все числа Мерсенна и Ферма – взаимно простые.

Необходимо отметить, что значения чисел Мерсенна и Ферма быстро растут. Это не позволяет использовать лишь их в качестве модуле СОК.

При работе же на двоичных компьютерах, иногда желательно выбирать модули

в виде чисел Мерсенна