На данный момент на генерацию простого числа с 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 простые числа такой длины?
Простой