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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

60
(n – 1)
st
, будет сравнимой с 1 по mod n. Об этом явлении будет сказано в
следующей главе, когда будут рассматриваться порядки чисел по модулю n.
Для степени 3, с другой стороны, действительно нет степени меньше, чем
(n – 1)
st
, которая сравнима с 1 по mod n. Назовём 3 примитивным корнем по
модулю n.
Ясно, что достаточно трудно замаскировать составное число под про-
стое на всех шагах, как это соответствует минимальным требованиям за-
ключения теоремы Ферма (первый шаг). Например, 341 и 561 являются оба
составными и они раскрывают свои свойства во время вышеприведённых
вычислений на стадиях
(в) и (г). C другой стороны, 25 и 2047 (= 23 × 89) оба
являются составными, но они маскируют себя под простые числа на стади-
ях вышеприведённых вычислений (а) и (б).
Последовательность вычислений, описанная выше, называется тестом
Миллера (1976 г.). Составные числа, проходящие через этот тест, как простые,
называются сильно псевдопростыми по основанию b. Рассмотрим более осно-
вательно
эти числа. Все сравнения будут по модулю n, и используем обозна-
чение 〈 х〉 для наименьшего положительного вычета числа х (mod n).
16.1. Тест Миллера по основаию b. Пусть n будет нечётным поло-
жительным целым числом > 1, и пусть b будет взаимно простым с n.
Шаг 1: Пусть k = n – 1, 〈 b
k
〉 = r. Если r = 1, то продолжаем, в против-
ном случае, n не выдерживает теста.
Пока k является чётным и r = 1, повторять следующее:
Шаг 2: Заменить k на k/2 и заменить r на новое значение 〈 b
k
〉 .
Когда k при проверке оказывается нечётным числом или r, не рав-
ным 1, то:
если r = 1 или n – 1, тогда n проходит тест.
Если r ≠ 1 и r ≠ n – 1, тогда n не проходит тест.
16.2. Определение. Если n – составное число и проходит тест Мил-
лера по основанию b, тогда n называется сильным псевдопростым числом
по основанию b.
Мы надеемся, как следует из проведенного выше обсуждения, если
n – простое число и n не делит b (так что (b, n) = 1), тогда n всегда пройдёт
тест Миллера по основанию b.
Решающим
фактом будет то, что х
2
≡ 1 (mod n), что предполагает х ≡
≡ ±1 (mod n), когда n является простым числом, так что не может появиться
вычета другого, кроме ±1 (т. е., 1 или n – 1), а тест Миллера не сможет его
отбросить. Конечно, шаг 1 точно соответствует теореме Ферма. Зарегистри-
руем этот факт следующим образом:

Страницы