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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

54
13.4. Компьютерные упражнения
1. Пусть m = (2
2
)
5
+ 1, a = 3, n = m – 1. Проверьте, что a
n
не сравнимо
с 1 (mod m). Это показывает, конечно, что m, пятое число Ферма, не являет-
ся простым. Позднее мы дадим тест Пепина для оценки принадлежности
числа к простым для F
k
= (2
2
)
k
+ 1; это упражнение является примером этого
теста.
2. Достаточно редкое явление для чисел вида a
p-1
быть сравнимыми с
1 не только по mod p, как требует теорема Ферма, но и по mod p
2
. Простые
числа, для которых это выполняется при a = 2, называются «простыми чис-
лами Вифериха», так как в 1909 А. Виферих рассматривал такие числа в
связи с «последней теоремой Ферма». Многое неизвестно о таких простых
числах, например, насколько их много. Вооруженные степенным алгорит-
мом в вышеприведенном виде, Вы можете это проверить для себя.
Сравнение a
p–1
≡ 1 (mod p
2
) выполняется для следующих пар (a, p)
(для очень больших чисел Вам потребуется extended точность!):
(2, 1093), (2, 3511);
(19, 3), (19, 13), (19, 43), (19, 137), (19, 63 061 489);
(41, 29), (41, 1 025 273), (41, 138 200 401).
Заметим, что для заданного числа р решение сравнения а
p–1
≡ 1 (mod p
2
)
может быть найдено методом «примитивных корней».
13.5. Проект: простые числа Вифериха. Добавляя подходящий цикл в
программу степенного алгоритма, проверим, что для а = 2 существуют только
простые числа p < 4000, удовлетворяющие выражению a
p–1
≡ 1 (mod p
2
), кото-
рые указаны выше, в п. 13.4 (2). (Действительно, не существует другого из-
вестного решения для а = 2). Также для а = 19 покажите, что единственные
решения, скажем, для р < 1000 уже приведены выше. Для а = 53 найдите че-
тыре простых числа меньших 100, которые удовлетворяют сравнению.
14. Псевдопростые числа
14.1. Определение. Пусть b будет положительным целым числом.
Положительное целое число n может быть названо псевдопростым по ос-
нованию b, при условии, что b – составное число, а b
n
≡ b (mod n). Заметим,
если (b, n) = 1, тогда n будет псевдопростым числом по основанию b, если и
только если b составное число, а b
n–1
≡ 1 (mod n). Действительно, некоторые
авторы включают (b, n) = 1 в определение псевдопростого числа по основа-
нию b, но мы используем более общее определение.
Ясно, что псевдопростые числа по основанию 1 не вызывают особого
интереса.

Страницы