Главная | Обратная связь

Возведение в степень и нахождение порождающего элемента группы.

Приведенный ниже шаблон реализует так называемое «наивное» модульное возведение в степень в конечном поле. Для примера взято поле F₁₉. Заносим его элементы в первую строку таблицы, а в ячейку A2 вводим формулу согласно рис. 7.

Рис. 7. Исходная формула

Распространяем формулу на диапазон ячеек A2:R18

Рис. 8. Таблица Кэли с выделенными примитивными элементами

В результате получилась таблица Кэли для возведения в степень по модулю 19. Особое внимание обратим на столбцы, выделенные серым цветом. В них многократное применение операции умножения к заглавным элементам столбцов образует полную перестановку элементов поля. Такие элементы называют порождающими или примитивными. Кроме того, следует обратить внимание на последнюю строку таблицы (все единицы). Она хорошо иллюстрирует малую теорему Ферма:

На практике наивное возведение в степень оказывается неэффективным. Приведем алгоритм бинарного модульного возведения в степень. В основе алгоритма лежит схема Горнера. Проиллюстрируем ее на конкретном примере [8]:

Что в итоге дает вместо 26 умножений – 4 возведения в квадрат + 3 умножения. Для больших чисел экономия становится еще более значительной. Заметим, что последовательность возведений в квадрат и удвоений соотносится с двоичным представлением показателя степени:

Начиная со второго старшего двоичного разряда 1 – возвести в квадрат и домножить, 0 – возвести в квадрат.

Алгоритм бинарного модульного экспоненцирования [1]:

Представить показатель степени в двоичном виде:

Присвоить

Для i от 1 до r: ;

Задача 2.3. Возвести число x в степень y по модулю числа N, используя метод бинарного модульного экспоненцирования.

Пример решения.

Дано: x = 134 y = 344 N = 365	Решение:
	yi
Найти:
xy mod N