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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

34
Тогда получим I ≈
1
3
h
(y
0
+ y
2n
+ 2(y
2
+ y
4
+ . . .+ y
2
n–2
) + 4(y
1
+ y
3
+. . . y
2
n
– 1
)),
где y
i
= f(x
i
)].
7.4. Проект: функция Римана. Несколько более заманчиво
в качестве упражнения использовать функцию
11
1
35
2
111
() () ( ) ( ) ( ) ...
235
Ri x Li x Li x Li x Li x=− − − +
У Вас без сомнения вызывает интерес вопрос, каким будет следую-
щий член разложения! Несомненно, что
π
(x)/Ri (x) → 1 при х → ∞, быстрее,
чем в ранее рассмотренных случаях. Эксперименты с числами, полученны-
ми ранее, продолжим, используя даже первые члены разложения Ri(x).
Дальнейшее подтверждение результатов может быть найдено на последней
стадии: см. ниже, п. 8.10.
7.5. Время на определение принадлежности к простым числам пу-
тём пробного деления.
Представим пример по использованию теоремы о
простых числах для оценки времени, необходимого для определения про-
стоты пробным делением. Чтобы доказать, что число n простое, необходимо
оценить результат пробного деления на простые числа, вплоть до
n
, а
также
n
/ln
n
. Выберем n = 10
k
, что означает пробное деление до пример-
но 10
k/2
/((k/2) ln 10) числа. Примем, очень оптимистично, что пробное деле-
ние числа 10
6
происходит каждую секунду, тогда времени для доказательст-
ва того, что данное число простое, потребуется примерно
22
14
6
10 10
2,75 10
( )(ln10)(10 60 60 24 365)
2
kk
k
k
−
=⋅ ⋅
⋅⋅⋅⋅
лет.
Даже для достаточно скромного числа k = 30 (30-значное простое
число) это время приближается к 11 месяцам, а для k = 50 оно доходит до
5,5 × 10
9
лет. Для k = 100 оно больше, чем 2,75 × 10
34
лет. Таким образом,
представлено доказательство того, что определение простоты путём проб-
ного деления реально неосуществимо для достаточно больших чисел.
В этом пособии мы ограничили такие доказательства числами, меньшими
10
10
, чтобы придать интерес к другим методам доказательства простоты
числа. Приведённые здесь вычисления должны показать, что использование
пробного деления непрактично, даже при использовании больших компью-
теров.
8. Решето Эратосфена
8.1. Компьютерные упражнения
1. Измените программу для получения простых чисел ≤ 5000.

Страницы