Индексы и их свойства. Определение дискретного логарифма

Пусть g – первообразный корень по модулю m (m = p ^a или m = 2 p ^a, p – простое нечетное число), c = j(m). Тогда множество чисел

                                         (1)

образует приведенную систему вычетов по модулю m. Поэтому для любого числа a взаимно простого с числом существует число gⁱ из множества (1) сравнимое с ним по модулю m: т.е.

                        .                             (2)              

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

Обозначается индекс символом ind _g a или короче, когда ясно, о каком основании идет речь.

Теорема 1. Для любого целого числа a взаимно простого с m по любому модуля m = p ^a или m = 2 p ^a, где p – простое нечетное число,   индекс ind _g a существует, и для любых целых чисел a, b взаимно простых с m выполняются свойства:

1⁰ a º b (mod m) тогда и только тогда, когда ind _g a º ind _g b (mod j(m));

2⁰ ind _g (ab)º ind _g a + ind _g b (mod j(m));

3⁰ если b | a, то ind _g (a/b)º ind _g a - ind _g b (mod j(m));

4⁰ если n Î N, то ind _g aⁿ º n ×ind _g a (mod j(m)).

Доказательство. Доказательство существования индекса следует из рассуждений в начале параграфа. Первое свойство следует из свойства первообразного корня.

Докажем свойство 3⁰. Пусть ind _g (ab) = i, ind _g a = j,  ind _g b = k. Тогда по определению индекса имеем:

Отсюда

Тогда по свойству первообразного корня i º j + k (mod j(m)).

Свойства 3⁰ и 4⁰ доказываются аналогично.ÿ

В силу свойств 1⁰-3⁰ индекса числа a по основанию g и по модулю m называют иногда дискретным логарифмом числа a. Задача вычисления дискретного логарифма трудная задача. Одним из методов вычисления дискретного логарифма ind _g a является метод перебора:

Чтобы найти ind _g a необходимо начиная, например с n = 0, сравнивать элемент a с элементом gⁿ  по mod m: если a º gⁿ (mod m), то ind _g a = n, в противном случае находим g^{n +1} º gⁿ g (mod m) и опять сравниваем элемент a с элементом g^{n + 1} и т.д. Если модуль m большой, то количество операций умножения, необходимое для вычисления дискретного логарифма велико.

Существует алгоритм, позволяющий существенно уменьшить время вычисления дискретного логарифма.

Теорема 2. Пусть t, r  - натуральные числа, r ² ³ t. Для любого целого числа l можно указать такие целые числа x и y, что

l º xr+y (mod t); 0£ x < r, 0 £ y < r.                        (3)  

Доказательство. Можно предполагать, что 0£ l < t. Полагаем

.

Имеем

.

С другой стороны,

,

поэтому

или

.ÿ

Теорема 2. Пусть g – первообразный корень по модулю m (m = p ^a или m = 2 p ^a, p – простое нечетное число), c = j(m). Тогда ind _g a можно найти, выполнив не более операций умножения по mod m.                       

Доказательство. Пусть +1. Рассмотрим ряды вычетов

                                         (4)

                                  (5)

Если сравнение разрешимо относительно l, то по теореме 2 l представимо в виде (3). Тогда

имеет место тогда и только тогда, когда

,                                           (6)

т.е. когда найдется элемент ряда (4), который сравним с каким-нибудь элементом ряда (5).

Сосчитаем число операций, позволяющих установить равенство (6). Для вычисления ряда (4) необходимо выполнить не более r -2 умножения по mod m. Для вычисления требуется выполнить не более  умножения по mod m и не более r -1 умножений для вычисления всех членов ряда (5). Поэтому число операций умножения для решения сравнения (6) не более

. ÿ

Справедлива следующая теорема.

Теорема 4. Пусть g – первообразный корень по модулю m (m = p ^a или m = 2 p ^a, p – простое нечетное число), c = j(m) = r ₁× r ₂ ×…× r_k,1< r ₁< c,…, 1< r_k < c. Тогда ind _g a можно найти, выполнив не более

операций умножения по mod m, где .

Для маленьких модулей составляются таблицы индексов.

Пример 1.  Составить таблицу индексов по mod 19.

Первообразный корень по модулю 19 равен 2 (см. пример 2 параграфа 2). Вычисляем по модулю 19:

                   

Таблица индексов по mod 19 имеет вид:

a	0	1	2	3	4	5	6	7	8	9
0	-	0	1	13	2	16	14	6	3	8
1	17	12	15	5	7	11	4	9	10	-

Пример 2.  Вычислить ind _g 234, ind _g -100 индексов по mod 19.

Так как 234 º 6(mod 19), то ind _g 234º14(mod 18).

Так как -100 º 14(mod 19), то ind _g -100º7(mod 18).

Пример 3.  Найти x, y если по mod 19 ind _g x = 24, ind _g y = 39.

Так как ind _g x = 24 º6(mod 18), то x º 7(mod 19).

Так как ind _g y = 39 º3(mod 18), то y º 8(mod 19).

Теорема 5. Пусть m = p ^a или m = 2 p ^a, p – простое нечетное число, c = j(m), НОД(m, c) = d. Тогда сравнение

                                               (7)

разрешимо тогда и только тогда, когда d | (ind _g b - ind _g a),  при этом в случае его разрешимости оно имеет d решений по mod m.

Доказательство.   По теореме 1 сравнение (7) равносильно сравнению

n × ind _g x × º ind _g b - ind _g a (mod c)                                     (8)

Последнее сравнение (8) линейное относительно ind _g x. Оно разрешимо тогда и только тогда, когда d делит (ind _g b - ind _g a). При этом в случае разрешимости сравнение (8) имеет   d решений по mod с:

ind _g x º y ₁(mod с),…, ind _g x º y_d (mod с),

которые дают d решений сравнения (7) по mod m:

.ÿ

Пример 4.  Решить сравнение . Перейдем к индексам и получим:

Тогда по таблице индексов находим x º 14(mod 19), то x º 5(mod 19).

Определение 2. Пусть (a, m) = 1. Число a   называется вычетом n -й степени по mod m, если сравнение

                                               (9)

разрешимо.

Теорема 6. Пусть (a, m) = 1. Число a   является вычетом n -й степени по mod m, тогда и только тогда, когда d |ind _g a. В приведенной системе вычетов по                                       по mod m имеется ровно с/ d вычетов n -й степени по mod m.

Доказательство.   Первая часть теоремы следует из теоремы 5.

По свойству индекса, если a пробегает приведенную систему вычетов по mod m, то ind _g a пробегают по mod с все числа множества 0, 1,…, с -1. Среди чисел последнего множества имеется с/ d чисел кратных d. Поэтому сравнение

n × ind _g x × º ind _g a (mod c),

а поэтому и сравнение (9) разрешимо для с/ d чисел a из приведенной системы вычетов по mod m. ÿ

Теорема 7. Пусть (a, m) = 1. Число a   является вычетом n -й степени по mod m тогда и только тогда, когда

.                                                   (10)

Доказательство.   Разрешимость сравнения (9) равносильна условию

.

Последнее сравнение равносильно условию

.

Последнее по свойству индекса равносильно условию (10).ÿ

Пример 5.  Так как 3 делит ind 7=6 по mod 19, то число 7 является вычетом 3-й степени по mod 19. В приведенной системе вычетов по mod 19 имеется 18/3 = 6 вычетов 3-й степени: 1, 7, 8, 11, 12, 17.