Первый шаг работы
алгоритма RSA — генерация двух простых чисел p и q заданного размера (например, 1024 бита каждое — одинаковый размер повышает криптостойкость).
Насколько я понял, для решения задачи перебора простых чисел до некоторого заданного предела предназначены:
—
Решето Эратосфера
—
Решето Сундамана
—
Решето Аткина (быстрый, современный)
Однако задача генерации простого числа заданного размера решается обычно (?) методом проб, т.е.
1) Генерируем случайное целое число заданного размера;
2) Проверяем его на простоту;
3) Если простое — PROFIT, если не простое — посторяем с п. 1.
Проверка на простоту в п. 2 осуществляется уже при помощи
других методов.
Так вот, мне интересна наиболее быстрая имплементация (желательно Python) какого-либа из подходов, т.е. функция
def get_prime(nbits):
""" Вот это интересно """
а также любая другая помощь/информация по теме.
