Асимптотический закон распределения простых чисел.

Решето Эратосфена отыскивает все простые числа от 1 до N. Однако при большом N поиск простых чисел таким способом отнимает много времени. Современная практическая криптография требует использования больших простых чисел – в некоторых стандартах используются простые числа размером порядка 1024 бита.

По понятным причинам, невозможно организовать поиск таких больших простых чисел при помощи решета Эратосфена. В настоящее время разработано несколько вероятностных и детерминированных тестов на простоту. Эти тесты определяют, является ли наугад выбранное число простым или составным. Далее мы изучим такие вероятностные тесты, как тест Ферма, Соловея-Штрассена, Миллера-Рабина.

Для поиска простых чисел с помощью таких тестов используют следующий подход: из чисел заданного диапазона случайным образом выбирают числа и проверяют их на простоту. Поиск прекращается как только будет найдено простое число. Такой подход называют случайным поиском простых чисел.

Для того чтобы оценить время, которое придется затратить на случайный поиск в заданном диапазоне, необходимо знать, сколько примерно простых чисел в этом диапазоне содержится. Конечно, точное распределение простых чисел в N неизвестно, но некоторые сведения об этом распределении у современной математики имеются. Так, в п.4 мы привели теоремы Евклида о простых числах, в которых утверждается, что, с одной стороны, простых чисел бесконечно много, а значит найдется сколь угодно большое простое число, а с другой стороны – что для любого m найдутся m подряд идущих составных, то есть существуют такие сколь угодно длинные диапазоны, на которых простых чисел нет вообще.

Более точно на вопрос о распределении простых чисел в N отвечает асимптотический закон распределения простых чисел.

Итак, обозначим π(x) – количество простых чисел, меньших либо равных x. Тогда справедлив

Асимптотический закон простых чисел

.

Другими словами, при x→∞, π(x)→x/lnx.

Кроме того, справедлива

Теорема Чебышева (1850 г.)

Для любого x при некоторых c1<1< c2 выполняется .

Учитывая асимптотический закон, можно сказать, что чем x больше, тем c1 и с2 ближе к 1.

Для x>1 с2<1,25506, для x≥17 с1=1.

 

Пример.

Пользуясь асимптотическим законом, вычислим примерное количество простых 512-битных чисел (таких, чтобы старший, 512-й, бит был равен 1).

Наименьшее значение 512-битного числа составляет 2511, наибольшее – 2512-1.

Таким образом, нужно найти приблизительное количество K простых чисел из диапазона (x1=2511, x2=2512).

K = π(x2)—π(x1) ≈ = = = = = .

Тогда вероятность при случайном поиске в заданном диапазоне выбрать простое число составляет

P = = .

Если же случайный поиск производить только среди нечетных чисел, то

P = .

То есть для того, чтобы путем случайного перебора среди 512-битных нечетных чисел найти простое, в среднем понадобится 178 итераций.

Для 1024-битных чисел поиск среди нечетных чисел потребует в среднем 355 итераций.

В общем, при увеличении требуемого размера числа (в битах) в 2 раза, среднее время поиска тоже увеличивается в два раза.

 


Функция Эйлера.








Дата добавления: 2015-11-28; просмотров: 2273;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.