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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

77
2. Найдите все значения k, 1 ≤ k ≤ 70, для которых k ⋅ 10
12
+ 1 является
простым числом. (Итак, начнём с теста Миллера, чтобы сократить боль-
шую часть значений
k). Вы найдёте k = 18, которое по основанию а = 7
обеспечит это. Следующим будет
k = 63, и несколько проще здесь исполь-
зовать тест Лукаса и найти различные основания для различных простых
чисел
q
i
= 2, 3, 5, 7.
3. Покажите, что
k ⋅ 3
25
+ 1 будет составным для 1 ≤ k ≤ 33, а k = 34, 42
и 70 все дадут простые числа.
4. Пусть
n = 10
12
+ 61. Проверьте, что n – 1 = 2
2
⋅ 5 ⋅ 3947 ⋅ 12 667 849
является разложением на простые сомножители
n – 1 и, отсюда, покажите,
что
n – простое число. Также покажите, что 10
12
+ 63 является простым
числом, используя разложение на простые сомножители 10
12
+ 62. Таким
образом, мы нашли пару
сдвоенных простых чисел.
5. Представим пример, где используется двухстадийный процесс. Пусть
n = 10
13
+ 37, так что n – 1 = 2
2
m, где m = 25 ⋅ 10
11
+ 9. Так как m > 10
10
, пока-
жите, что оно простое тем же самым методом.
6. Проверьте, что 10
15
+ 36 = 2
2
⋅ 7 ⋅ 37 ⋅ 965 250 965 251, и покажите,
что последний сомножитель является простым, благодаря факторизации
965 250 965 250 и использования теста
n – 1 над q. Отсюда покажите,
что10
15
+ 37 является простым числом.
7. Приведём довольно впечатляющий пример. Для нахождения боль-
ших величин основания
а для проверки выполнение условия, что а
(n–1)/2
не
сравнимо с 1 (mod
n), потребовалось число n = 26 437 680 473 689. Вы мо-
жете проверить, что все числа
а < 500 дают а
(n-1)/2
≡ 1 (mod n). (Почему этого
достаточно, чтобы убедиться, что
а – простое число?).
Используйте разложение на простые множители числа
n – 1 = 2
3
⋅ 3
2
⋅ 11 ⋅ 41
2
⋅ 89 ⋅ 347 · 643, которое несложно проверить, исполь-
зуя соответствующую программу. Докажите, что
n – простое число.
8. Проверьте разложение на простые множители числа
n – 1 = 2 · 31 ×
× 258 629 069 для n = 16 035 002 279 и используйте тест Лукаса, чтобы до-
казать, что
n – простое число. Также проверьте, что 2n + 1 является про-
стым числом, например, используя п. 3.1. Проделайте то же самое для
n = 15 048 973 639, разлагая на множители сначала n – 1.
9. Покажите, что
n = 30 059 924 764 123 – простое число, используя
тест
n – 1 над q (в противоположность пункту (8) простое число 2 не вызыва-
ет сложностей, в то время, как для числа 3 имеются некоторые проблемы).
10. Определите вероятностные простые числа вида
n = r
4
+ 1 для
1900
≤ r ≤ 2000. Выбранные значения должны быть 1900 + k, где k = 10, 16,
26, 32, 34, 42, 44, 48, 52, 56, 62, 72, 78, 86, 94. Найдя простые делители числа
(
n – 1), мы получаем материал для определения простых сомножителей r.
Проверьте все эти числа
n, которые на самом деле являются простыми на
основе теста
n – 1 над q.

Страницы