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

UptoLike

Рубрика: 

56
2. Приведём намётки доказательства того, что существует бесконечно
много псевдопростых чисел по основанию 2. Действительно, это даёт то,
что если n нечётное псевдопростое число по основанию 2, тогда N = 2
n
– 1.
Заметим, что, так как это n cоставное, тогда найдём N, используя разложе-
ние на множители. Воспользуйтесь теоремой Ферма, чтобы показать, что
2
n
– 2 = kn для некоторого k, и докажите, что N | (2
N–1
– 1). (Воспользуйтесь
ещё раз разложением на множители).
3. Может ли 2
n
– 2 когда-нибудь быть псевдопростым числом по ос-
нованию 2? На этот вопрос утвердительно ответил У. Л. МакДаниэль
(1989). Пусть n = 465 794; проверьте, используя степенной алгоритм, что
2
n
3 (mod (n – 1)). Докажите, что
)12()12(
321
n
n
и, отсюда, что при
N = 2
n
– 2, мы получим 2
N
2 (mod N), так что, действительно, N является
псевдопростым числом по основанию 2.
Несмотря на вышеприведенное заключение в пункте (2), псевдопростые
числа по основанию 2 встречаются значительно реже, чем простые числа.
Действительно, существует 882 206 716 простых чисел, меньших, чем 2 × 10
10
,
но только 19 865 псевдопростых простых чисел по основанию 2 находятся в
этом диапазоне. Итак, если встречается число, могущее быть псевдопростым
числом по основанию 2, то существует «очень большой шанс», что на самом
деле оно простое. Конечно, вероятность повышается, если тестировать на
псевдопростое число по более, чем одному основанию, например, 2, 3 и 5.
Существуют числа, проходящие
через эту сеть тоже. Действительно, сущест-
вуют числа, проходящие через все тесты на псевдопростое число, но которые
являются составными, как мы это сейчас покажем.
14.7. Определение. Составное число n, которое удовлетворяет
сравнению b
n–1
1 (mod n) для всех b, являющихся взаимно простыми с n,
называется числом Кармайкла (в честь Р. Д. Кармайкла, который пред-
ставил их в 1912 г.).
Конечно, давая определение, мы не доказали, что такие числа сущест-
вуют, но приведём пример. Пусть n = 561 = 3 11 17. Таким образом,
(b, 561) = 1 означает, что (b, 3) = (b, 11) = (
b, 17) = 1. Используя теорему
Ферма,
b
2
1 (mod 3) предполагает, что b
560
= (b
2
)
280
1 (mod 3);
b
10
1 (mod 11) означает, что b
560
= (b
10
)
56
1 (mod 11);
b
16
1 (mod 17) означает, что b
560
= (b
16
)
35
1 (mod 17).
Так как 3, 11 и 17 являются тремя различными простыми числами, то
это означает, что b
560
1 (mod 561).
Похожий прием можно применить для получения общего результата.