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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

76
20.2. Компьютерное упражнение: цепи Каннигхэма простых чисел
Проверьте, что
р
1
= 1 122 659 является простым числом путём проб-
ного деления. Сколько членов содержит последовательность
р
1
, р
2
=2 р
1
+ 1, р
3
= 2 р
2
+ 1, . . .
простых чисел? Вы, конечно, можете проверить принадлежность чисел ряда
к простым пробным делением, но, вместо этого, попытайтесь использовать
п. 20.1. Такие ряды простых чисел называются цепями Каннигхэма. Суще-
ствуют две другие длинные цепи, начинающиеся с 2 164 229 и 2 329 469.
20.3. Упражнения
1. Используйте метод, аналогичный п. 20.1, чтобы показать, что если
р является простым числом и 2
р
≡ 1 (mod 2p + 1), тогда 2р + 1 будет про-
стым числом. Как этот результат связан с п. 20.1? Будет ли аналогичным ре-
зультат для
a
p-1
≡ 1(mod 2p + 1) для некоторого другого основания а?
2. Пусть
р будет нечётным простым числом и n = ap + 1, где а – чёт-
ное число, 2
≤ n <
p
. Предположим, что 2
n-1
≡ 1 (mod n) и (2
а
– 1, n) = 1.
Покажите, что для некоторого простого числа
q, на которое делится n, что
порядок 2
а
mod q будет равен р, и докажите, что p | (q– 1). Теперь покажите,
что
q >
n
, и докажите, что n – простое число. Результат может быть ис-
пользован для анализа цепей простых чисел вида
р
1
, р
2
= а р
1
+ 1, р
3
= а р
2
+ 1, . . .
Интерпретация теоремы 20.1. Предположим, что n удовлетворяет
заключению теоремы Ферма, т. е.,
n является либо простым, либо псевдо-
простым числом по основанию
а. Предположим также, что a
(n–1)/ q
не срав-
нимо с 1 для делителя
q числа n – 1 (в случае п. 20.1, q = p, так что (n –
–1)/
q = 2). Тогда n будет простым числом. Наиболее полезный общий ре-
зультат рассматриваемого плана был сформулирован Е. Лукасом в немного
более слабой форме в 1891 г., но доказан Д. Г. Лемером в 1927 г.
20.4. Теорема (тест на простоту числа (n – 1) над q, или тест Лукаса)
Предположим, что а
n-1
≡ 1 (mod n), но для любого простого числа q,
которое делит (n – 1), мы будем иметь а
(n-1)/q
не сравнимо с 1 (mod n). То-
гда n будет простым числом
.
20.5. Компьютерные упражнения
1. Используйте тест Миллера, чтобы показать, что n = k ⋅ 10
8
+ 1 явля-
ется составным числом для 1
≤ k ≤ 12 , за исключением, возможно, k = 6 и
k = 7. Теперь используйте тест Лукаса, чтобы показать, что k = 6 и k = 7
должны дать простые числа. Вспомните, что Вы должны испытать несколь-
ко различных оснований перед тем, как найдёте нужное. [Конечно, этого
довольно мало, чтобы проверить также и пробным делением предложенные
Вами аргументы на работоспособность для чисел < 10
10
].

Страницы