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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

51
ление результатов в таблицу дает (используем символ d для обозначения
бита в разложении):
d r
r (mod 11)
a
a (mod 11)
0 1 1 7
2
5 (d = 0, так что r остается 1)
1 7
2
5 7
4
3 (d = 1, так что r:= r ⋅ a = 1 ⋅ 5)
0 7
2
5 7
8
9 (d = 0, так что r не изменяется)
0 7
2
5 7
16
4 (d = 0, так что r не изменяется)
1 7
18
9 7
32
5 (d = 1, так что r = r
.
⋅ a = 5 ⋅ 4)
1 7
50
1 7
64
3 (d = 1, так что r = r ⋅ a = 9 ⋅ 5)
так что окончательно 7
50
≡ 1 (mod 11).
Аналогично двоичное представление десятичного числа 24 будет
11 000, и 7
24
= 7
8
×
7
16
. Если мы представим его по mod 25, тогда 7
2
≡ 1, так что
все последовательные степени 7
4
, 7
8
, . . . будут 1, а 7
24
≡ 1(mod 25). Заметим,
что это имеет вид а
р–1
≡ 1 (mod p), где р не является простым числом!
12.8. Упражнение
Покажите, что 3
50
≡ 9 (mod 20). Найдите двоичное представление 341 и
проверьте, что 2
340
≡ 1(mod 341). (Тяжелым шагом является доказательство,
что 32
2
≡ 1(mod 341)). Заметьте, что это другое составное число
(341 = 11 ⋅ 31), удовлетворяющее заключению теоремы Ферма для a = 2.
Замечание. Максимальное значение модуля, которое можно исполь-
зовать для безопасного извлечения квадратного корня составляет примерно
10
9
для extended. Это относится к числам, которые перемножаются между
собой, и они могут быть такими же большими, как модули.
12.9. Компьютерные упражнения
1. Используйте программу для представления 7
24
(mod 25) и
2
240
(mod 341) и оцените относительно вопросов, поставленных перед этим.
Также проверьте, что 5
280
≡ 67 (mod 561), 5
560
≡ 1 (mod 561) и, что
100
560
≡ 1 (mod 561).
2. Найдите 17
3313
и 3313
17
(mod 112 643). Как бы Вы поступили, чтобы
найти НОД (p
q
– 1, q
p
– 1), где р = 17 и q =3313? (Будьте немного осторожны
в ответе. Так как р ≡ 1 и q ≡ 1 (mod 16) НОД, несомненно, делится на 16).
Что Вы скажете относительно НОД ((p
q
– 1) / (p–1), (q
p
– 1)/(q –1))?
3. Проверьте, если позволит точность, что 3
1 373 652
≡1 (mod 1 373 653).
Также найдите разложение на сомножители 1 373 653, чтобы доказать, что
оно не простое число. Проверьте, что a
m
≡ a (mod m), и что m не является
простым числом в следующем случае (a, m) = (2, 161 038), (2, 215 326),
(2, 314 821), (3, 314 821), (5, 314 821), (7, 314 821).

Страницы