Количество нечетных целых чисел, которые мы должны проверить, пока не найдем то, которое является простым для любого произвольного размера модуля RSA.

Популярные размеры модуля RSA: $1024$, $2048$, $3072$ и $4092$ кусочек. Сколько в среднем случайных нечетных целых чисел нам нужно проверить, пока мы не ожидаем найти одно простое число? Я знаю примерно каждый $\ln р$ целые числа имеет простое число. Для $1024$ кусочек $р$, $\ln р = 710$. В среднем нужно протестировать около $710/2=355$ нечетные числа, прежде чем найти простое. Верно ли это и можем ли мы извлечь формулу $(\ln р)/2$ для любого произвольного размера модуля RSA?

Для n-битного RSA вам нужно найти два простых числа, произведение которых является n-битным числом, то есть примерно n/2 бит каждое. На самом деле один немного меньше, а другой немного больше, потому что вы не хотите, чтобы простые числа располагались слишком близко друг к другу.

Примерно одно из ln M чисел вокруг M является простым числом; это натуральный логарифм. ln (2) близко к 0,7. Если M = 2^(n/2), то ln M ≈ 0,35n. Вы проверяете только нечетные целые числа, которые в два раза чаще являются простыми, с вероятностью 2/0,35n. Проверка 0,175n нечетных целых чисел находит простое число. Вам нужно два, так что около 0,35n.

Но обратите внимание, что многие из них имеют маленькие делители и могут быть идентифицированы очень быстро; например, с помощью сита, удаляющего числа с коэффициентами < 1000 или 10 000. Чтобы принять простое число, вы проведете тест Миллера-Рабина 50 или 100 раз, в то время как для 3/4 не простых чисел вы выполните его один раз, для 3/4 остальных — дважды и т. д. Дело в том, что проверка не простого числа на простоту обычно выполняется довольно быстро.Тестирование двух реальных простых чисел занимает много времени. Количество составных частей, которые вы проверяете на простоту, не имеет большого значения.

PS Я только что понял, что все переоценивают в 2 раза. Скажем, я решил, что мне нужно простое число около некоторого нечетного K, поэтому я проверяю K, K+2, K+4 и т. д., пока не наткнусь на простое число. Пусть p — наибольшее простое число, меньшее K, а q — первое простое число >= K. Количество неверных чисел для проверки — это не промежуток q-p, разделенный на 2 (поскольку мы проверяем только нечетные числа), а половина этого числа, поскольку K может быть где угодно в этом промежутке.

PPS Я только что понял, что с этим аргументом что-то не так…

Нет, ты ошибаешься, потому что

Я знаю, что примерно у каждого ln p целых чисел есть простое число.

это грубая оценка, которая на самом деле неверна.

Оценка функции счета простых чисел $\Pi(p)=p /ln(p)$ оценивает общее количество простых чисел от 0 до $р$. Итак, для числа с x битами вам нужно посмотреть на $\Pi(2^{x}) - \Pi(2^{x-1})$ и сравните его с общим количеством кандидатов, которые $2^{х-2}$, когда вы рассматриваете только нечетные числа.

Вы не за горами, и разница невелика для больших чисел, но формула не так проста.