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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

58
проверка того, что они являются наименьшими значениями m после m = 1, а
одно (если захотите) найдёте в п. 14.9 (1)).
4. Пусть р = 187 687, q = 375 373, r = 43 355 467. В действительности
все представленные числа – простые. Невыполнимо, даже с использованием
повышенной точности, проверить, что n = pqr является числом Кармайкла,
так как pqr очень большое число. Отсюда покажите, что условие, что
n – 1
делится на р –1, q – 1 и r – 1, эквивалентны следующему:
(p – 1) | (qr – 1), (q – 1) | (pr – 1), (r – 1) | (pq – 1).
Можно проверить эти условия с использованием повышенной точно-
сти; постарайтесь сделать это. Также замените r на 6 404 784 751 (также
простое число) и проделайте то же самое. Эти три числа имеют вид 6m + 1,
12m + 1, 18mk + 1 для подходящих значений
m и k; сравните с вышеприве-
дённым п. 14.9 (1).
14.11. Проект: числа Кармайкла. Найдите все 16 чисел Кармайкла,
которые <10 000. (Не забудьте о результате п. 14.9 (2)). Также найдите все
числа Кармайкла, которые являются произведением трёх простых чисел,
каждое из которых <100.
15. Теорема Вильсона
15.1. Теорема Вильсона. Целое число р > 1 является простым, если и
только если (р –1)! ≡ – 1 (mod p).
15.2. Упражнения
1. Пусть p = 4k + 1 будет простым числом. Теорема Вильсона утвер-
ждает, что (4k)! ≡ –1(mod p). Рассмотрите члены 2k + 1, . . . , 4k, появляю-
щиеся в произведении, дающем (4 k)!, и покажите, что в действительности
((2 k)!) 2 ≡ (4 k)! (mod p). Докажите, что х
2
≡ –1(mod p) имеет решения х =
= ±(2 k)! (Исходя из вышеприведённой леммы 12.5, существуют только два
решения).
2. Покажите, что р и (р + 2) будут оба простыми числами («двойные
простые числа»), если и только если 4((р – 1)! + 1) + р ≡ 0 (mod p(р + 2)).
[Подсказки для «если». Покажите, что р – нечётное, предполагая, что р –
чётное, и используйте
сравнение для получения противоречия. Используйте
сравнение, чтобы показать, что (р – 1)! + 2 ≡ 0 (mod р), и докажите, что р –
простое число с помощью теоремы Вильсона. Теперь используйте 4 (р –
– 1)! + 2 ≡ 0 (mod р + 2), чтобы показать, что (р + 1)! + 1 ≡ 0 (mod р + 2), и
докажите, что (р + 2) – простое число]. В качестве критерия того, что р и
p + d оба простые
числа, снова используйте теорему Вильсона.

Страницы