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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

61
16.3. Теорема. Если тест Миллера даёт отрицательный результат
по основанию b, тогда n – составное число.
Заметим, что расчёты, произведённые в начале данного раздела, пока-
зывают, что 25 является сильным псевдопростым числом по основанию 7, а
2047 будет сильным псевдопростым числом по основанию 2.
16.4. Упражнения
1. Пусть n будет нечётным числом, n ≥ 3. Почему n всегда будет про-
ходить тест Миллера по основанию n – 1? [В сравнении по модулю n, (n – 1)
может быть заменен на (–1)].
2. Предположим, что, выполняя тест Миллера над n по основанию b, мы
получили для некоторого r ≥ 0,
()
1/2
r
n
b
−
≡ 1 (mod n), но
()
1
1/2
r
n
cb
+
−
=
не сравнимо
с 1(mod n), где 2
r+1
| n – 1. Почему по основанию b тест Миллера для числа n
даёт отрицательный результат? Покажите, что (c – 1, n) является собственным
делителем n. [Вы должны доказать, что делитель не равен 1 и n]. В примере (в)
в начале этого раздела для с = 32, n = 341 получено (c – 1, n) = 31, в то же вре-
мя в примере (
г) (c – 1, n) = 33. Этот метод обеспечивает нахождение собст-
венных делителей любого псевдопростого числа n по основанию b (где
(b, n) = 1), для которого тест Миллера по основанию b даёт отрицательный ре-
зультат. (Конечно, даже если b
n–1
≡ с не сравнимо с 1 (mod n), тогда (c – 1, n)
является собственным делителем n).
16.5. Программа теста Миллера. Необходимо реализовать тест
Миллера в виде программы для ЭВМ.
Замечание. Как следует из вышеизложенного, мы считаем, что у Вас
имеется программа, включающая алгоритм Хэда. Если это не так, тогда вычис-
ления с модулями, большими, чем корень квадратный из машинной точности
(более, чем 10
9
для повышенной точности), будут сделаны с ошибками.
16.6. Компьютерные упражнения
1. Проверьте, что n = 1 373 653 проходит тест Миллера по основаниям 2
и 3. Теперь проверьте, что n – составное число, используя соответствующую
программу. Следовательно, n является сильным псевдопростым числом по ос-
нованиям 2 и 3. (Оно будет наименьшим). Проверьте, что n не выдерживает
теста Миллера по основанию 5; действительно, оно не является чётным псев-
допростым числом по основанию 5;
отрицательный ответ на тест Миллера по-
лучается на шаге 1. Однако, если 5
n–1
≡ c (mod n), тогда (c – 1, n) = 829 собст-
венный делитель n. (Сравните с вышеприведённым в п. 16.4 (2)).
2. Проверьте, что n = 25 326 001 является сильным псевдопростым
числом по основаниям 2, 3 и 5 (они наименьшие). Проверьте, что n не явля-
ется четным числом, псевдопростым по основанию 7, но, несмотря на это,

Страницы