Первообразные корни (Первообразные корни и дискретные логарифмы)

2

Первообразные (примитивные) корни

Определение. Число a, взаимно простое с m, принадлежит показателю d, если d - наименьшее натуральное число, для которого a^d mod m = 1.

Определение. Число, принадлежащее показателю (m) ((m) – функция Эйлера), называется первообразным (примитивным) корнем по модулю m.

Свойство. Пусть число a - взаимно простое с m, и a принадлежит показателю d, тогда числа a⁰, a¹, a²,… a^d-1 попарно несравнимы по модулю m.

Доказательство. Допустим aⁿ  a^k mod m и k < n. Разделим обе части сравнения на a^k. Получим a^n-k  1 mod m. Тогда n-k должно быть кратно показателю d и не может быть меньше d. То есть среди чисел a⁰, a¹, a²,… a^d-1 пары aⁿ  a^k mod m нет.

Следствие. Если a – первообразный корень по модулю m, ряд a⁰, a¹, a²,… a^(m)-1 представляет собой совокупность всех взаимно простых с m чисел, меньших m. То есть a^k пробегает приведенную систему вычетов при k = 1, 2,… (m).

Примеры. Находим первообразные корни чисел 2, 3, … m по модулю m.

a^x mod 7  2 первообразных корня

a^x mod 11  4 первообразных корня

a^x mod 9  2 первообразных корня

a^x mod 8  нет первообразных корней!

Теорема. Пусть p – нечетное простое (то есть простое, не равное 2). Тогда по модулям вида p^k и 2 p^k , k = 1, 2, 3,… существуют первообразные корни.

Доказательство смотри в книге Ю.С.Харин и др. «Математические и компьютерные основы криптологии»

Множество чисел меньших m и взаимно простых с m (приведенная система вычетов) образует циклическую мультипликативную группу, причем первообразный корень является образующим элементом этой группы.

Дискретный логарифм

Определение. Пусть b - натуральное число, взаимно простое с m и a^x mod m = b, тогда число x называется дискретным логарифмом числа b по модулю m при основании a или индексом числа b по модулю m при основании a. Обозначается: x = ind_a b или без указания основания: x = ind b.

В приведенных выше табличных примерах дискретные логарифмы (индексы) для чисел взаимно простых с модулем (строки с желтыми заголовками) находятся в заголовках столбцов - ячейках с зеленым фоном. Как видно из примеров, однозначность определения дискретного алгоритма обеспечивается только в том случае, когда основанием a является первообразный корень. Причем, для того чтобы дискретные логарифмы существовали для всех чисел, меньших модуля m, необходимо чтобы m было простым числом, то есть взаимная однозначность и замкнутость операций возведения в степень и дискретного логарифмирования выполняется только в поле Галуа.

Свойство. Дискретный логарифм произведения равен сумме логарифмов:

ind_a bc = ind_a b + ind_a c (mod m).

Доказательство. Перемножим по модулю m степени b = a^{ind b} mod m и c = a^{ind c} mod m.

Получим bc mod m = a^{ind b+ind c} mod m, что и требовалось доказать.

Свойство. Показатель степени выносится как множитель за знак дискретного логарифма:

ind_a b^k = k ind_a b (mod m).

Доказательство. Полагаем сначала k = 2 и, опираясь на предыдущее свойство дискретного логарифма, по индукции доказываем равенство для любого k.

А.В.Бруханский