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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

92
14. Напишите программу для определения всех решений уравнения
(3) для любого
а (сравнимого с 1 mod 8) и k (в пределах расширенной точ-
ности). Программа должна распечатать последовательные значения
s, полу-
ченные при изменении от 3 до
k. Когда а = 9, почему все значения s равны
1? [Намёк. 3
2
= 9]. Проверьте работу Вашей программы тестированием для
малых значений
а и k. Проверьте, что четырьмя решениями (mod 2
30
) вида
х
2
≡ 17 (mod 2
30
) будут
х = 204 265 751, 332 605 161, 741 136 663, 869 476 073.
15. а) предположим, что
n ≥ 1 и 12
2
+=
n
n
F является простым чис-
лом. Покажите, что
F ≡ 5 (mod 12), и докажите, что
3
1.
F
⎛⎞
=
−
⎜⎟
⎝⎠
Это означает,
что
k = 3 является всегда подходящим значением при использования теста
Пепина для чисел Ферма. Покажите, что 5 также является подходящим зна-
чением, как и 10;
б) используйте тест Пепина (и программу степенного алгоритма) или
другой способ для проверки на простоту числа Ферма, пока точность ЭВМ
Вам это позволит.
в) покажите, что
5
1,
p
⎛⎞
=
⎜⎟
⎝⎠
p является нечётным простым числом, если и
только если
р ≡ ±1 (mod 10), а
7
1,
p
⎛⎞
=
⎜⎟
⎝⎠
если и только если р ≡ ±1 или ±3, или
±9 по (mod 28). (В последнем случае сначала убедимся, что квадратичные
вычеты по mod 7 равны 1, 2 и 4). Если Вам хочется побольше практики, до-
бавим ещё несколько результатов:
3
1,
p
⎛⎞
−
=
⎜⎟
⎝⎠
если и только если р ≡ 1 (mod 6),
5
1,
p
⎛⎞
−
=
⎜⎟
⎝⎠
если и только если р ≡ 1, 3, 7 или 9 (mod 20),
11
1,
p
⎛⎞
=
⎜⎟
⎝⎠
если и только если р ≡ ±1, ±5, ±7, ±9 или ±19 (mod 44).
23.2. Проект. Напишите программу, которая моделировала бы от-
правление сообщений между двумя абонентами. Все необходимые состав-
ляющие представлены в программе, реализующей метод с использованием
эллиптических кривых. Добавьте возможность отправки подписи.
23.3. Упражнения
1. Рассчитайте следующие выражения вручную:
1711 1711 1711 1711
,,,.
1999 2007 2021 2027
⎛⎞⎛⎞⎛⎞⎛⎞
⎜⎟⎜⎟⎜⎟⎜⎟
⎝⎠⎝⎠⎝⎠⎝⎠
Для каких знаменателей k Вы можете с уве-
ренностью доказать, что 1711
Rk ?

Страницы