Определение. Число, принадлежащее показателю φ(m) (φ(m)– функция Эйлера), называется первообразным (примитивным) корнем по модулю m.
Свойство. Пусть число a - взаимно простое с m, и a принадлежит показателю d, тогда числа a0,
a1, a2,…ad-1 попарно несравнимы по модулю m.
Доказательство. Допустим
anº akmod m и
k < n. Разделим обе части сравнения на ak. Получим
an-k
º 1
mod m. Тогда n-k должно быть кратно показателю d и не может быть меньше d. То есть среди чисел a0, a1, a2,…ad-1 пары anº akmod m нет.
Следствие. Если a – первообразный корень по модулю m, ряд a0, a1, a2,…a φ(m)-1 представляет собой совокупность всех взаимно простых с m чисел, меньших m. То есть akпробегает приведенную систему вычетов при k = 1, 2,… φ(m) .
Примеры. Находим первообразные корни среди чисел 2, 3, … φ(m) по модулю m.
ax mod 7 φ(7) = 6 2 первообразных корня
|
a \ x |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
2 |
2 |
4 |
1 |
2 |
4 |
1 |
|
|
3 |
3 |
2 |
6 |
4 |
5 |
1 |
3 - первообразный корень |
|
4 |
4 |
2 |
1 |
4 |
2 |
1 |
|
|
5 |
5 |
4 |
6 |
2 |
3 |
1 |
5 - первообразный корень |
|
6 |
6 |
1 |
6 |
1 |
6 |
1 |
|
ax mod 11 φ(11) = 10 4 первообразных корня
|
a \ x |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
2 |
2 |
4 |
8 |
5 |
10 |
9 |
7 |
3 |
6 |
1 |
2 - первообразный корень |
|
3 |
3 |
9 |
5 |
4 |
1 |
3 |
9 |
5 |
4 |
1 |
|
|
4 |
4 |
5 |
9 |
3 |
1 |
4 |
5 |
9 |
3 |
1 |
|
|
5 |
5 |
3 |
4 |
9 |
1 |
5 |
3 |
4 |
9 |
1 |
|
|
6 |
6 |
3 |
7 |
9 |
10 |
5 |
8 |
4 |
2 |
1 |
6 - первообразный корень |
|
7 |
7 |
5 |
2 |
3 |
10 |
4 |
6 |
9 |
8 |
1 |
7 - первообразный корень |
|
8 |
8 |
9 |
6 |
4 |
10 |
3 |
2 |
5 |
7 |
1 |
8 - первообразный корень |
|
9 |
9 |
4 |
3 |
5 |
1 |
9 |
4 |
3 |
5 |
1 |
|
|
10 |
10 |
1 |
10 |
1 |
10 |
1 |
10 |
1 |
10 |
1 |
|
ax mod 9 φ(9) = 6 2 первообразных корня
|
a \ x |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
2 |
2 |
4 |
8 |
7 |
5 |
1 |
2 - первообразный корень |
|
3 |
3 |
0 |
0 |
0 |
0 |
0 |
не взаимно простое с 9 |
|
4 |
4 |
7 |
1 |
4 |
7 |
1 |
|
|
5 |
5 |
7 |
8 |
4 |
2 |
1 |
5 - первообразный корень |
|
6 |
6 |
0 |
0 |
0 |
0 |
0 |
не взаимно простое с 9 |
|
7 |
7 |
4 |
1 |
7 |
4 |
1 |
|
|
8 |
8 |
1 |
8 |
1 |
8 |
1 |
|
ax mod 8 φ(8) = 4 нет первообразных корней!
|
a \ x |
1 |
2 |
3 |
4 |
|
|
1 |
1 |
1 |
1 |
1 |
|
|
2 |
2 |
4 |
0 |
0 |
не взаимно простое с 8 |
|
3 |
3 |
1 |
3 |
1 |
|
|
4 |
4 |
0 |
0 |
0 |
не взаимно простое с 8 |
|
5 |
5 |
1 |
5 |
1 |
|
|
6 |
6 |
4 |
0 |
0 |
не взаимно простое с 8 |
|
7 |
7 |
1 |
7 |
1 |
|
Теорема. Пусть p – нечетное простое (то есть простое, не равное 2). Тогда по модулям вида pkи 2pk, где k= 1, 2, 3,…, существуют первообразные корни.
Доказательство см. в книге Ю.С.Харин и др. «Математические и компьютерные основы криптологии»
Множество чисел меньших m и взаимно простых с m представляет собой циклическую мультипликативную группу, причем первообразный корень является образующим элементом этой группы.
В приведенных выше табличных примерах дискретные логарифмы (индексы) для чисел взаимно простых с модулем (строки с желтыми заголовками) находятся в заголовках столбцов - ячейках с зеленым фоном. Как видно из примеров, однозначность определения дискретного алгоритма обеспечивается только в том случае, когда основанием a является первообразный корень. Причем, для того чтобы дискретные логарифмы существовали для всех чисел, меньших модуля m , необходимо чтобы m было простым числом, то есть, взаимная однозначность и замкнутость операций возведения в степень и дискретного логарифмирования выполняется только в поле Галуа.
Свойство . Дискретный логарифм произведения равен сумме логарифмов:
inda bc = inda b + inda 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 , что и требовалось доказать.
Свойство . Показатель степени выносится как множитель за знак дискретного логарифма:
inda bk = k inda b (mod m ).
Доказательство . Полагаем сначала k = 2 и, опираясь на предыдущее свойство дискретного логарифма, по индукции доказываем равенство для любого k .
А.В.Бруханский
Скачать в формате MS Word 2000 (zip-файл 15 Кбайт)