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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

63
сутствовали простые числа! (Вы должны найти точно пять сильных псевдо-
простых чисел).
16.9. Проект. Напишите программу, чтобы показать, что наименьшее
число, которое является и сильным псевдопростым числом по основанию 2,
и числом Кармайкла, будет 15 841.
16.10. Проект. Существует простое исследование, которое делает
программу теста Миллера более элегантной. Пусть двоичное представление
(n – 1) выглядит как d
k
d
k-1
. . . d
1
d
0
, где каждое d
i
будет 1 или 0, а d
k
= 1. То-
гда 1) число (n – 1) будет чётным, если d
0
= 0; 2) при этом условии двоичное
представление для (n – 1)/2 будет d
k
d
k-1
. . . d
1
. Вставим это в программу
теста Миллера. (Делает ли это изменение выполнение программы более бы-
стрым?).
17. Вероятностное тестирование на простоту
Как было показано ранее, наименьшим для системы сильных псевдо-
простых чисел по основаниям 2, 3 и 5 есть 25 326 001. Таким образом (ис-
пользуя этот результат), любое число, меньшее, чем 25 326 001 может быть
либо простым, либо составным, что нужно учитывать для максимум трёх
применений теста Миллера. Мы здесь не предлагаем следовать этому мето-
ду доказательства принадлежности
к простым числам, так как существуют
и другие интересные методы, которые не требуют нахождения системы
наименьших псевдопростых чисел по выбранным основаниям. Однако важ-
но отметить, что в некотором смысле большинство тестов Миллера (по раз-
личным основаниям), по которым прогоняются числа, «выглядят пригод-
ными» для нахождения простых чисел.
17.1. Теорема. Пусть n будет нечётным и составным. Тогда n про-
ходит тест Миллера, минимум, по (n – 1)/4 основаниям при условии
1 ≤ b ≤ n – 1.
Заметьте, теорема говорит о том, что отсутствует «строгая» аналогия
с числами Кармайкла: n никогда не может быть сильным псевдопростым
числом по любому основанию. Непрактично проверять по (n – 1)/4 основа-
ниям, когда n
велико, но можно неформально рассудить таким образом: да-
но целое число n и выбрано «случайное» основание b из диапазона
1 ≤ b≤ n – 1. Предположим, что n проходит тест Миллера по основанию b.
Вероятность того, что для составного числа n пройти тест по одному из вы-
бранных оснований b, не превышает
1
4
, так что вероятность того, что число
n является составным не превышает
1
4
. (Ясно, что, при самом плохом выбо-
ре, b будет либо 1, либо n – 1. См. выше, п. 16.4 (1)). Более того, если мы

Страницы