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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

78
11. Покажите, что 1+ 8 ⋅ 3 ⋅ 5 . . . 23 = 892 371 481 является простым
числом (произведение содержит все простые числа от 3 до 23).
12. Можно показать, что 10
27
– 1 = 3
5
⋅ 37 ⋅ 757 ⋅ 333 667 ⋅ n, где
n = 440 334 654 777 631. Используйте программу для факторизации n – 1
(это число имеет только один простой делитель
r > 10
5
и он < 10
10
) и, отсю-
да, покажите разложение на простые сомножители числа 10
27
– 1.
13. Это достаточно длительное упражнение. Используя тождества
a
2
–
–
b
2
= (a – b)(a + b) и a
3
+ b
3
= (a + b)(a
2
– ab + b
2
), разложите число 10
48
– 1,
насколько сумеете, на простые сомножители. Одним из сомножителей будет
10
16
– 10
8
+ 1. Докажите, что это простое число с помощью теста n – 1 над q.
Отсюда полностью разложите 10
48
– 1 на простые сомножители и, следова-
тельно, полностью факторизуете число 11 . . . 1, состоящее из 48 единиц в
десятичной форме.
Тест
n – 1 над q требует знания всех простых чисел, на которые де-
лится
n – 1; возможно улучшение этого теста, когда требуется только
«большинство» из простых делителей.
20.6. Заключение. (Теорема Прота (Ф. Прот, 1878))
Пусть n = k ⋅ 2
m
+ 1, где m ≥ 2, k является нечётным числом и k < 2
m
.
Предположим, что существует а такое, что a
n
– 1
≡ –1 (mod n). Тогда n бу-
дет простым числом
.
Предположение, что
a
(n
– 1)/2
≡ –1 (mod n), не является слишком жёст-
ким: если
n является простым числом, тогда степенью будет ± 1 (mod n), и
если она равна + 1, то желательно попробовать другое
а. Для нечётного
простого числа
а, что желательно, величина а будет «квадратичным невы-
четом по mod
a».
20.7. Компьютерное упражнение. Используйте теорему Прота и
подходящую программу для нахождения простых чисел в следующих ря-
дах: 3
⋅ 2
m
+ 1, 5 ⋅ 2
m
+ 1, 7 ⋅ 2
m
+ 1, для всех 20 ≤ m ≤ 41. Вы могли бы прове-
рить, являются ли составными числами те, для которых теорема Прота даёт
отрицательный результат, используя тест Миллера. (Для первой серии зна-
чения
m выберите 30, 36 и 41).
20.8. Заключение. Предположим, что n = hp
k
+ 1, где р является не-
чётным простым
числом, а h является чётным, h < p и k ≥ 1. Предполо-
жим, что существует а такое
, что a
n
– 1
≡ 1 (mod n) и (a
(n–1)/р
, n) = 1. Тогда
n будет простым числом
.
20.9. Проект. Результат п. 20.8 может быть использован для нахожде-
ния цепей простых чисел, подобных цепям Каннигхэма (см. выше, п. 20.2).
Выбирая
k = 1 в п. 20.8 и начиная с р = 3 и h = 2, мы получим, что 2 ⋅ 3 +

Страницы