Как ускорить генерацию простых чисел? Какой размер простых чисел нужен для 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 простые числа такой длины?
Как ускорить генерацию простых чисел? Какой размер простых чисел нужен для 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 простые числа такой длины?
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 простые числа такой длины?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для RSA обычно используют простые числа длиной от 1024 бит. Увеличение длины числа увеличивает безопасность системы RSA. Ваш код для генерации простых чисел работает правильно, но для достижения требуемой скорости генерации вам может понадобиться оптимизация.
Во-первых, можно использовать более эффективный алгоритм проверки числа на простоту, например, тест Миллера-Рабина. Этот алгоритм обычно более быстрый и дает достаточно хорошее качество проверки простоты числа.
Во-вторых, можно улучшить оптимизацию функции генерации простых чисел. Например, можно использовать сито Эратосфена для предварительной фильтрации чисел, которые явно не являются простыми.
Также можно параллельно генерировать несколько простых чисел одновременно, чтобы увеличить скорость генерации.
Наконец, можно использовать специализированные библиотеки или программное обеспечение для генерации простых чисел, которые оптимизированы для работы с большими числами.
В целом, ускорить генерацию простых чисел можно за счет оптимизации алгоритмов и хорошей параллельной реализации.