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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

62
7
n–1
≡ c (mod n) даёт (c – 1, n) – собственный делитель n. (Сравните с выше-
приведённым п. 16.4 (2)).
3. Убедитесь, что следующие числа проходят тест Миллера по осно-
ваниям 2, 3 и 5:
(а) 14 386 156 093, (б) 15 579 919 981, (в) 18 459 366 157,
(г) 19 887 974 881, (д) 21 276 028 621.
Применяя тест Миллера по основанию 7 к n, равному каждому из (а),
(б) и (г), найдите (как в вышеприведённом п. 16.4 (2))
с, для которого
c
2
≡ 1 (mod n). [Это с является последним вычетом, найденным тестом Мил-
лера]. Найдя (c – 1, n), определите собственный делитель n. Даёт ли он соб-
ственный делитель для (в) и (д)?
4. Имеем несколько чисел, которые являются сильными псевдопро-
стыми числами по основаниям 2, 3 и 5. Проверьте, могут ли они факторизо-
ваться как выше, в п. (3),
используя основание 7 (или, возможно, 11):
(а) 1 157 839 381, (б) 3 215 031 751, (в) 3 697 278 427,
(г) 5 764 643 587, (д) 6 770 862 367.
Cчитая, что Вы можете факторизовать (б), покажите, что оно тоже яв-
ляется числом Кармайкла.
5. Используйте тест Миллера, чтобы показать, что числа k ⋅ 10
8
+ 1,
1 ≤ k ≤ 12, являются все составными, за исключением, возможно, k = 6 и k = 7.
(Для некоторого k, например, k = 2 тест Миллера особенно необходим!).
6. Используйте тест Миллера (или что-нибудь другое, что придёт в
голову) на числах от 5 000 000 до 5 000 100 для нахождения простого числа.
Используйте тест Миллера для нахождения первого числа > 5 ⋅10
8
, которое
могло бы быть простым.
16.7. Проект. Приспособьте программу теста Миллера для измерения
числа шагов до точки, где тест заканчивается (в результате получения не-
чётного показателя степени или вычета, отличного от 1 или n – 1). Теперь
попробуйте простые числа одно за другим из файла и выберите фиксиро-
ванное основание b, например, 2. Измените программу таким образом, что-
бы она выдавала на
печать простое число р, для которого количество шагов
в тесте Миллера наибольшее среди некоторого количества предыдущих
простых чисел. Например, когда b = 2, Вы можете найти, что тест Миллера
для р = 2 имеет один шаг, для р = 3 имеет три шага, для р = 17 имеет три
шага (а именно, 2
16
≡ 1, 2
8
≡ 1, 2
4
= 16 ≡ –1 (mod 17)), для р = 73 имеет четы-
ре шага, для р = 257 имеет шесть шагов (так что наименьший р, имеющий
семь шагов, более 257), р = 6529 имеет восемь шагов. Как было указано ра-
нее, большое количество шагов показывает, что наименьшей степенью b по
сравнению с (n – 1)
st
будет ≡ 1 (mod n).
16.8. Проект.
Найдите все сильные псевдопростые числа по основа-
нию 2, которые меньше, чем 10 000. Обеспечьте, чтобы в этом списке от-

Страницы