@Bleno-git

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

На данный момент на генерацию простого числа с 512 знаками уходит приблизительно 4-15 секунд (у меня довольно мощная машина), но требуются числа с 1024 знаками, а так время генерации может достигать нескольких минут. Требуется скорость до 5-10 секунд, причём 100% не больше 10 сек. Данный код генерирует простые числа заданной длины:

def isPrime(n, k=20):
	if n == 2 or n == 3:
		return True
	if not n & 1:
		return False

	def check(a, s, d, n):
		x = pow(a, d, n)
		if x == 1:
			return True
		for i in range(s - 1):
			if x == n - 1:
				return True
			x = pow(x, 2, n)
		return x == n - 1

	s = 0
	d = n - 1

	while d % 2 == 0:
		d >>= 1
		s += 1

	for i in range(k):
		a = random.randrange(2, n - 1)
		if not check(a, s, d, n):
			return False
	return True
def genPrime(n):
    	n = n + 1 if n % 2 == 0 else n + 2
    	while not isPrime(n):
    		n += [1,6,5,4,3,2,1,4,3,2,1,2,1,4,3,2,1,2,1,4,3,2,1,6,5,4,3,2,1,2][n % 30]
    	return n
genPrime(random.randint(10**length, 10**(length + 1)))


Где length - длина числа. Как можно ускорить генерацию чисел, и нужно ли вообще для RSA простые числа такой длины?
  • Вопрос задан
  • 242 просмотра
Пригласить эксперта
Ответы на вопрос 2
@deliro
1. Взять нормальный алгоритм
2. Переписать на Cython
Ответ написан
Комментировать
Если цель получить число, то
from Crypto.Util import number
number.getPrime(2048)

Если цель получить число и написать код генерации самому, то реализуйте это
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы