Алгоритм RSA
Страница 8. Множество простых чисел для криптосистемы RSA

Множество простых чисел для криптосистемы RSA

Как доказано Эвклидом более двух тысяч лет назад, существует бесконечное множество простых чисел. Поскольку алгоритм RSA оперирует с ключами определенной длины, то количество возможных простых чисел конечно, хотя тем не менее очень велико. По теореме о Простых Числах количество простых чисел меньших некоторого n асимптотически приближается к n = ln(n). Следовательно, количество простых чисел для ключа длиной 512 битов или меньше приблизительно составляет 10**^{150 (десять в степени 150)}. Это больше, чем количество атомов в известной Вселенной.