быстрое вычисление наибольшего простого множителя 512-битного числа в питоне

Question

Я моделирую свою криптографическую схему в Python, я новый пользователь для нее.

p = 512-битное число, и мне нужно рассчитать наибольший простой множитель для него, я ищу две вещи:

1. Самый быстрый код для обработки этой большой простой факторизации
2. Код, который может принимать 512 бит числа в качестве ввода и может обрабатывать его.

Я видел разные реализации на других языках, весь мой код написан на python, и это последний момент, когда я застрял. Итак, дайте мне знать, если есть какая-либо реализация в Python.

Пожалуйста, объясните в простой, как я новый пользователь Python

извините за плохой английский.

edit (взято из ответа ОП ниже):

#!/usr/bin/env python
def highest_prime_factor(n):
   if isprime(n):
      return n
   for x in xrange(2,n ** 0.5 + 1):
      if not n % x:
         return highest_prime_factor(n/x)

def isprime(n):
   for x in xrange(2,n ** 0.5 + 1):
      if not n % x:
         return False
   return True

if  __name__ == "__main__":
   import time
   start = time.time()
   print highest_prime_factor(1238162376372637826)
   print time.time() - start

Приведенный выше код работает (с небольшой задержкой) для "1238162376372637826", но расширяя его до

10902610991329142436630551158108608965062811746392 57767545600484549911304430471090261099132914243663 05511581086089650628117463925776754560048454991130443047

заставляет питона сходить с ума. Есть ли способ, чтобы, как и выше, я могу иметь это посчитали в кратчайшие сроки?

Answer 1

Для решения на основе Python вы можете захотеть взглянуть на pyecm В системе, в которой также установлен gmpy, pyecm обнаружил следующие факторы:

101, 521, 3121, 9901, 36479, 300623, 53397071018461, 1900381976777332243781

Там все еще есть 98-значный нефакторный композит:

60252507174568243758911151187828438446814447653986842279796823262165159406500174226172705680274911

Факторинг этого оставшегося композита с использованием ECM может быть непрактичным.

Редактировать: Через несколько часов, оставшиеся факторы

6060517860310398033985611921721

и

9941808367425935774306988776021629111399536914790551022447994642391

Answer 2

Это должно лучше подходить, чем тривиальный подход для больших чисел (хотя при таком разборе чисел каждая чистая реализация Python займет некоторое время): Простая факторизация Полларда * 100 * * * 1003

Answer 3

Если вы можете установить расширение, gmpy поможет - посмотрите мой ответ на этот ТА вопрос , в частности, функцию def prime_factors(x) в коде, который я там показываю.

В чистом Python (без какого-либо расширения) это немного сложнее и намного медленнее, см., Например, код здесь (но не задерживайте дыхание, пока оно работает на ваших огромных числах; - ).

Answer 4

('''==============================================================================='''
>        '''              CALCULATE  HIGHEST PRIME
> FACTOR                                  '''
>
> '''===============================================================================''')
>
> #!/usr/bin/env python
> def highest_prime_factor(n):
>    if isprime(n):
>       return n
>    for x in xrange(2,n ** 0.5 + 1):
>       if not n % x:
>          return highest_prime_factor(n/x)
> def isprime(n):
>    for x in xrange(2,n ** 0.5 + 1):
>       if not n % x:
>          return False
>    return True
> if  __name__ == "__main__":
>    import time
>    start = time.time()
>    print highest_prime_factor(1238162376372637826)
>    print time.time() - start

код работает с небольшой задержкой по номеру: «1238162376372637826», но расширяя его до (109026109913291424366305511581086089650628117463925776754560048454991130443047109026109913291424366305511581086089650628117463925776754560048454991130443047) заставляет питона сходить с ума Есть ли способ, как указано выше, я могу иметь это рассчитал это в кратчайшие сроки.