Элементы теории чисел и криптозащита. Воронков Б.Н - 50 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

50
ния: х ≡ 0, 2, 3, 5 (mod 6). Что Вы скажите относительно предположения,
что d | p – 1?
12.6. Упражнения
1. Докажите напрямую результат п. 12.4 для случая нечётного просто-
го числа р и d = 2.
2. Найдите решения сравнения x
d
≡ 1 (mod 11) для d = 2 и d = 5.
3. Найдите решения сравнения x
d
≡ 1 (mod 19) для d = 2, 3, 6 и 9.
4. Докажите, исходя из п. 12.4, что если d | p – 1 и а
d
≡ 1, а a
k
не срав-
нимо с единицей для 1 < k < d, тогда существуют d различных решений по
(mod p) для x
d
≡ 1, точно равные x = 1, a, a
2
, . . . , a
d–1
.
12.7. Степенной алгоритм
Если мы попробуем использовать теорему Ферма, особенно в плане
возможности доказательства того, что отдельно взятое число а не простое,
основываясь на условии, что n не делит a, мы получим, что а
n–1
не сравнимо
с 1 (mod n). Наихудшим возможным методом будет представление сначала
а
n
, а затем нахождение вычета по модулю n, тогда мы должны быть в со-
стоянии представлять большие числа с большими степенями по данному
модулю. Несколько более разумно представлять последовательные степени
а, а
2
, а
3
, . . . и приводить их по модулю n (находить вычеты по модулю n),
пока это возможно. (Заметим, что мы использовали здесь положение, что
если а
k
≡ b (mod n), тогда а
k+1
≡ ab(mod n)). Но существует и другой путь,
который значительно превосходит этот, позволяя очень большие степени
представлять с очень большой скоростью.
В качестве примера оценим 7
50
(mod 11). Сначала получим двоичное
представление 50:
50
=
25
⋅ 2 + 0
25
=
12 ⋅ 2 + 1
12
=
6 ⋅ 2 + 0
6
=
3 ⋅ 2 + 0
3
=
1 ⋅ 2 + 1
1
=
0 ⋅
.
2 + 1.
Таким образом, двоичное представление будет 110 010. (0 и 1 назы-
ваются «битами» представления числа). То есть,
50 = 0 ⋅
1 + 1 ⋅ 2 + 0 ⋅ 2
2
+ 0 ⋅ 2
3
+ 1 ⋅ 2
4
+ 1 ⋅ 2
5
, так что 7
50
= 7
0
⋅ 7
2
⋅ 7
0
×
×
7
0
⋅ 7
16
⋅ 7
32
.
Представляя r ≡ 7
50
(mod 11), мы задали а = 7, r = 1 и квадрат а на ка-
ждом шаге, так что а = 7
2
, 7
4
, 7
8
, 7
16
, . . . , умножая текущее значение r на те-
кущее значение а, если оно равно «1» в двоичном разложении 50. Оформ-

Страницы