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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

59
15.3. Компьютерное упражнение. Проверьте, что для р = 563, (р –
– 1)! ≡ –1 (mod p
2
).
15.4. Проект: простые числа Вильсона. Мы могли бы назвать про-
стое число р «простым числом Вильсона», если (р – 1)! + 1 будет совпа-
дающим с 0 не только по модулю р, но и по модулю р
2
. Напишите програм-
му для нахождения простых чисел Вильсона и, особенно, проверьте, что их
существуют только единицы <1000, а именно: 5, 13 и 563.
16. Тест Миллера
Рассмотрим следующие вычисления, все начинающиеся с проверки
того, что некоторое число n является простым или псевдопростым числом
по основанию b.
n = 25, b = 7 : 7
24
≡ 1, 7
12
≡ 1, 7
6
≡ –1 (mod 25).
(а)
n = 2047, b = 2 : 2
2046
≡ 1, 2
1023
≡ 1 (mod 2047).
(б)
n = 341, b = 2 : 2
340
≡ 1, 2
170
≡ 1, 2
85
≡ 32 (mod 341)
(в)
n = 561, b = 2 : 2
560
≡ 1, 2
280
≡ 1, 2
140
≡ 67 (mod 561).
(г)
n = 2243, b = 2 : 2
2243
≡ 1, 2
2242
≡ 1, 2
1121
≡ –1 (mod 2243)
(д)
В каждом случае мы удерживаем половину показателя до тех пор, по-
ка не произойдёт одно из двух событий: либо показатель станет нечётным
(как в (б), (в) и (ж)), либо вычет будет отличаться от 1 (как в (а), (в), (г) и
(д)). В (в) и (д) оба события
произошли на одном шаге.
Если мы начнём с нечётного простого числа n, что произойдёт?
Обычно b
n–1
≡ 1 (mod n) обеспечивается теоремой Ферма, а (n – 1) будет
чётным, так что мы можем записать b
(n–1)/2
= x. Так как х
2
≡ 1 (mod n) и n
является простым числом, что даёт х ≡ ±1 (mod n). Если у нас +1 и, если
(n – 1)/2 остаётся чётным, тогда мы можем продолжить представление
b
(n–1)/4
= y, и так как у
2
≡ 1 (mod n), то у нас снова будет у ≡ ± 1 (mod n).
Таким образом, продолжая в этом направлении, мы приходим либо к
вычету (–1) или нечётному показателю степени (или одновременно и
тому и другому на одном шаге), и после мы останавливаемся. (Если
х
2
≡ 1 (mod n), где n – простое число, то не существует достаточно полезно-
го предсказания конечного результата по х).
Заметим, что для заданного простого числа n количество шагов для
достижения вычета (–1) может сильно различаться для различных значе-
ний b. Например, для n = 257, мы получим 2
(n–1)/r
≡ 1 (mod n) для r = 1, 2, 4,
8, 16, 32, в то время как вычет будет (–1) для r = 64. С другой стороны, для
того же самого n 3
(n–1)/r
≡ 1 (mod n) для r = 1, но вычет (–1) будет для r = 2.
Конечно, это означает, что для b = 2 значительно меньшая степень 2, чем

Страницы