Материал: Лекция 2 Генерирование простых чисел [восстановлен]
Ответом на данный вопрос является следующая теорема.
Теорема [5]. Пусть П(n) – число простых чисел, которые ≤ n, тогда
|
|
|
lim |
Π(n) |
=1 |
|
|
|
|
|
|
|
|
||
|
|
|
n→∞ n / ln n |
/( −1.08366) |
|
||
Пример: n=1/( ) |
≤ ( ) ≤ |
|
|||||
Количество простых чисел ограничено сверху с снизу |
s |
||||||
|
|
|
|
|
|
|
|
|
000 000 |
|
|
|
|
||
|
П( ) |
|
72383 |
|
78543 |
|
|
Фактически |
|
= 78449 |
≤ П( ) ≤ |
|
|
||
Из этой теоремы можно получить аппроксимацию
доли нечетных
l-разрядных простых чисел в виде l ln210, т. е. среднее число попыток для генерирования l-разрядного
простого числа равно s = |
l ln (10) |
. |
|
|
|
|
|
||
2 |
|
|
|
|
(Для доказательства этого факта достаточно лишь |
|
|||
заметить, что количество в точности l-разрядных |
|
|||
нечетных чисел равно |
|
|
||
(10l −10l −1 ) / 2 .) |
|
|
||
Пример 1. Пусть l = 100, тогда s = l ln(10) |
= 100 ln(10) |
=115 |
||
2 |
2 |
|
||
Важнейшие тесты по проверке простоты чисел
Все тесты делятся на детерминированные и вероятностные.
Детерминированные тесты дают определенный ответ, является ли данное число простым или составным. Случайные (вероятностные) тесты дают такой же ответ, но с некоторой вероятностью (обычно близкой к 1) того, что он будет правильным.
До недавнего времени (до 2002 г.) не было известно ни одного детерминированного алгоритма с полиномиальной сложностью. В 2002 г. три индийских математика нашли такой метод [6]. Его сложность оказывается равной O((log n)12 ), хотя для специальных чисел вида 2p +1 сложность будет значительно меньше, а именно: O((log n)6 ). Ввиду значительной сложности этого алгоритма предпочтение, однако, отдается вероятностным алгоритмам, удовлетворяющим следующему условию.
Если n простое, то оно всегда проходит тест (т. е. то, что оно простое, определяется однозначно), если же оно составное, то может случиться, что оно пройдет тест, однако вероятность такого события может быть сделана сколь угодно малой.
Рассмотрим далее два важнейших примера подобных алгоритмов тестирования чисел на простоту.