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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

52
В каком из представленных случаев справедливо a
m–1
≡ a (mod m)?
4. Найдите решение сравнения х
4
≡ 1 (mod 821). (Так как 821 – про-
стое число, то существуют четыре решения, из которых два найти просто).
К вышеупомянутой программе можно добавить цикл.
5. Пусть m = 37 ⋅ 2
16
+ 1 = 2 424 833. Проверьте, что 37
32
≡ – 1 (mod m).
Теперь используем сравнение 37 ⋅ 2
16
≡ – 1 (mod m), со степенью, увеличенной
до 32, чтобы доказать, что m является делителем числа Ферма F
9
= (2
2
)
9
+ 1.
(Этот факт был обнаружен А. Е. Вестерном в 1903 г., но полная факторизация
F
9
была проведена только в 1990 г.).
6. Также как в пункте 5, примем m = 11131 ⋅ 2
12
+ 1 = 45592577. Уве-
личивая 11131 ⋅ 2
12
≡ – 1 (mod m) до подходящей степени, покажите, что m
является делителем (также простым) числа Ферма F
10
= (2
2
)
10
+ 1.
Обратите внимание на то, что число Ферма содержит 309 цифр! Этот
делитель был найден Д. Л. Селфриджем в 1953 г., но полная факторизация
F
10
произведена полвека спустя.
7. Существует много других примеров сомножителей k ⋅
2
n
+ 1 чисел
Ферма, некоторые из которых получены прямой атакой, как в предыдущих
двух примерах. Например, можете ли Вы найти малое число k такое, что
m = k ⋅ 2
25
+ 1, которое было бы сомножителем F
23
? (Представьте, что Вы
хотите увеличить k ⋅ 2
25
≡ – 1 (mod m) до соответствующей степени, такой,
что показатель 25 будет настолько близко, насколько возможно,
к 2
23
= 8 388 608). Вы можете проверить, что результирующий фактор m яв-
ляется простым числом.
12.10. Проект: р – 1 метод факторизации Полларда. Одной из вер-
сий этого метода факторизации будет следующая. Предположим, что р –
простое число, а k такое, что (р – 1) | k!. Почему это означает, что все про-
стые сомножители р – 1 будут < k ? Почему теорема Ферма утверждает, что
2 k! ≡ 1 (mod p)?
Предположим, что мы хотим разложить на множители данное целое
число
N. Возьмём малое целое число, скажем, 2 и вычислим последователь-
но 2
1
, 2
2
, 2
6
, 2
24
, . . . , 2
k!
все по (mod N), где k является разумно большим (но
не слишком большим!). Если р – простой сомножитель N, тогда, естествен-
но, р является сомножителем (〈 2
k!
– 1〉
N
, N) и, по счастливому стечению,
НОД будет р скорее, чем N. (Вспомните, что обозначение 〈 х〉
N
принято для
наименьшего положительного вычета x mod N). Напишите программу, осу-
ществляющую этот метод и проверьте её на числах, которые являются про-
изведением двух простых чисел. Заметим, что для успеха вычислений мы
должны потребовать, чтобы все простые сомножители искомого фактора р
были бы ≤ k.

Страницы