33.6. Степень элемента

Рассмотрим в мультипликативной группе вычетов Z* последовательность степеней некоторого элемента а:

а0, а1, а2, а3, (33.31)

Мы начинаем счёт с нуля, полагая a0 mod га = 1; г-й член последовательности равен a1 mod га. Например, последовательность степеней числа 3 по модулю 7 имеет вид

i 0123456789 10 11... Зг mod 71326451326 4 5 ...

а для степеней числа 2 по модулю 7 имеем

г 0123456789 10 11... 2г mod 71241241241 2 4 ...

В этом разделе под (а) мы будем понимать подгруппу группы Z*, порождённую элементом а, а под ordn(a) - порядок элемента а группы Z*. К примеру, (2) = {1,2,4} в группе Z*- и ordi(2) = 3. Применив к группе Z* следствие 33.19 и вспомнив определение у-функции Эйлера, получим такое утверждение:

Теорема 33.30 (теорема Эйлера)

Если га > 1 - целое число, то

а = 1 (mod га).(33.22)

для всякого а £ Z*

При простом га эта теорема превращается в «малую теорему Ферма»:

Теорема 33.31 (малая теорема Ферма) Если р > 1 - простое число, то

av~l = 1 (mod р)(33.23)

для всякого а £ Z* Доказательство

Поскольку число р - простое, <~р(р) = р - 1 (33.21).

Малая теорема Ферма применима ко всем элементам Zp, кроме нуля. Если умножить это сравнение на а. то получится сравнение ар = a (mod р), которое верно и для а = 0 (р - любое простое число).

Если ordra(g) = Z*, то все элементы Z* являются степенями элемента д. В этом случае д называется примитивным корнем (primitive root) или образующей (generator) группы Z*. Например, 3 является примитивным корнем в Z*-. Если группа Z* имеет образующей,

её называют циклической (cyclic). Имеет место следующая теорема (доказательство можно найти, например, в книге Нивена и Цукер-мана [151]). Теорема 33.32

Пусть га > 1. Группа Z* циклична тогда и только тогда, когда га равно 2, 4, имеет вид рк или 2рк (где р > 2 - простое число, а /г - целое положительное число).

Пусть д является образующей группы Z*. Тогда для всякого а £ Z* найдётся z, для которого gz = a (mod га). Такое z называют дискретным логарифмом (discrete logarithm) или индексом (index) элемента а £ Z* по основанию g и обозначают indrajfl(a).

Теорема 33.33 (о дискретном логарифме)

Пусть g является образующей группы Z*. Тогда сравнение дх = ду (mod га) равносильно сравнению ж = у (mod <р(п)). Доказательство

Если х = у (mod ¥>(га))) то есть ж = у + k<p(n) при некотором целом /г, то дж = дУ+к(р(п) = дУ (gv(n))k = ду -1к = ду (все равенства по модулю га).

Напротив, пусть дх = ду (mod га). Согласно следствию 33.18, последовательность степеней д периодична с периодом \(д)\ = (п), поэтому что ж = у (mod <*р(п)).

Мы видим, что величина indn(a) определена с точностью до слагаемого, кратного (р(п), то есть может рассматриваться как элемент аддитивной группы Ъ*пу

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

Теорема При простом р > 2 и положительном целом к уравнение

ж2 = 1 (mod рк)(33.34)

имеет ровно два решения (ж = ±1). Доказательство

Если ж2 = 1 (mod рк)1 то ж взаимно просто с р, поэтому решения надо искать в группе Z* (где га = рк); пусть д - образующая этой группы. Тогда уравнение (33.34) записывается в виде

(5"<*n,e(*))2 = gindn,g(i) (mod га).(33.35)

По теореме 33.33 это можно переписать как

2 • indntg(x) = 0 (mod (р(га)).(33.36)

(заметим, что индекс 1 равен 0). Такие уравнения мы уже решали в разделе 33.4; теорема 33.24 говорит, что (33.36) имеет ровно два решения (а мы знаем, что ж = ±1 подходит).

[Впрочем, можно было бы обойтись и без ссылки на теорему 33.32: если ж2 - 1 = (ж - 1)(ж + 1) делится на рк, то одна из скобок делится на р, тогда другая не делится, а значит, первая делится и на рк.]

Решение уравнения ж2 = 1 (mod га), не сравнимое по модулю га с ±1, называется нетривиальным квадратным корнем из 1 в Ъп (nontrivial square root of 1 modulo га). Например, 6 является нетривиальным корнем из 1 по модулю 35. Следующее утверждение понадобится нам в разделе 33.8 при обсуждении теста Миллера - Рабина.

Следствие 33.35

Если Ъп содержит нетривиальный корень из 1, то число га составное.

Доказательство

Очевидно вытекает из теоремы 33.8.

Вычисление степеней повторным возведением в квадрат.

Возведение в степень по модулю играет важную роль при проверке чисел на простоту, а также в криптосистеме RSA. Как и для обычных чисел, повторное умножение - не самый быстрый способ; лучше воспользоваться алгоритмом повторного возведения в квадрат (repeated squaring).

Пусть мы хотим вычислить аъ mod га, где а - вычет по модулю га, а Ь - целое неотрицательное число, имеющее в двоичной записи вид (bk, bk-\,... ,Ь\,Ьо) (число знаков считаем равным /г + 1; старшие разряды, как обычно, слева). Мы вычисляем ас mod га для некоторого с, которое возрастает и в конце концов становится равным Ь.

Modular-Exponentiation (a,b,n)

1с \gets О

2d \gets 2

3пусть \langle b k,b {k-l},\ldots,b 0\rangle ---

двоичная запись $Ь$

4for i \gets k downto О

5do с \gets 2c

6d \gets (d \cdot d) \bmod n

7if b i=l

8then с \gets c+1

9d \gets (d\cdot a) \bmod n

10return d

При умножении с на 2 число ас возводится в квадрат, при увеличении с на 1 число ас умножается на а. На каждом шаге двоичная запись с сдвигается на 1 влево, после чего, если надо (6г- = 1), последняя цифра двоичной записи меняется с 0 на 1. (Заметим, что переменная с фактически не используется и может быть опущена.)

Оценим время работы процедуры. Если три числа, являющиеся её исходными данными, имеют не более fi битов, то число арифметических операций есть O(fi), а число битовых - 0(/33).

Пример (а = 7, Ь = 560, га = 561) показан на рис. 33.4.

Упражнения