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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

64
последовательно выполним тест Миллера по k различным основаниям, ве-
роятность того, что прошло тест составное число, будет 1/4
k
. Таким обра-
зом, наша уверенность в том, что прошедшее тест число простое, возрастает
в k раз. Действительно, представленный метод, известный как вероятност-
ный метод выбора простых чисел Рабина, обычно используется для нахо-
ждения очень больших «вероятных простых чисел», записываемых 50 циф-
рами, а k бывает около 100. В своей оригинальной работе (1976 г.)
Миллер
показал, что, используя догадку, называемую обобщенной гипотезой Рима-
на, составное число n не проходит теста по основанию < 2(ln n)
2
. Например,
если n – составное число, приблизительно 10
50
, то это означает, что доста-
точно приблизительно 27 000 тестов Миллера, чтобы установить это.
17.2. Компьютерные упражнения
1. Приспособьте программу теста Миллера таким образом, чтобы она
делала, скажем, 10 случайных выборов основания b (1 ≤ b ≤ max) для числа
max, которое вводится вместе с n. Таким образом, Вам необходимо доба-
вить max и переменную расчетов, например, test в объявление VAR:
max, test : integer;
и программа сосчитает n и max ранее, чем n и b
. Вставьте
Randomize;
после объявления readln и вставьте цикл FOR (test:= 1 to 10), чтобы повто-
рить тест 10 раз. Основание будет выбираться по команде
base := Random (max – 1) + 2,
которая выбирает его среди случайных чисел, удовлетворяющих неравенст-
ву 2 ≤ b ≤ max.
Теперь применим многократный тест Миллера к примерам
пп. 16.6 (5) и (6), чтобы показать, останется ли «вероятное простое число»
таким же после
удлинённого теста. Вы, конечно, могли бы выбрать n – 1
(или n – 2) для max, но практически достаточно 100.
2. Найдите «вероятное простое число» вида n = r
4
+ 1, где
1900 ≤ r ≤ 2000. (Мы увидим далее, что для числа n, где n – 1 может доста-
точно просто разлагаться на сомножители, существует хороший метод для
доказательства того, что n действительно является простым числом).
3.* Предполагая, что количество простых чисел вида r
4
+ 1, где
1 ≤ r ≤ R, удовлетворяет выражению
∫
=
R
x
dx
RQ
2
ln
)(
λ
,
для больших R, где
λ
является константой. Принимая, что всё это выполне-
но, и, используя результаты п. (2), оцените значение
λ
.

Страницы