Теорема Чебышева (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 раза, среднее время поиска тоже увеличивается в два раза.

 


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



Дата добавления: 2018-11-26; просмотров: 769;


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

Воспользовавшись поиском можно найти нужную информацию на сайте.

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

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.008 сек.