fastest calculation of largest prime factor of 512 bit number in python

Question

dear all,

i am simulating my crypto scheme in python, i am a new user to it.

p = 512 bit number and i need to calculate largest prime factor for it, i am looking for two things:

1. Fastest code to process this large prime factorization
2. Code that can take 512 bit of number as input and can handle it.

I have seen different implementations in other languages, my whole code is in python and this is last point where i am stuck. So let me know if there is any implementation in python.

Kindly explain in simple as i am new user to python

sorry for bad english.

edit (taken from OP's answer below):

#!/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

The code above works (with a bit of delay) for "1238162376372637826" but extending it to

10902610991329142436630551158108608965062811746392 57767545600484549911304430471090261099132914243663 05511581086089650628117463925776754560048454991130443047

makes python go crazy. Is there any way so that just like above, i can have it calculated it in no time?

Answer 1

If you can install an extension, gmpy would help -- see my answer to this SO question, specifically the def prime_factors(x) function in the code I show there.

In pure Python (without any extension allowed) it's a tad harder and a lot slower, see the code here for example (but don't hold your breath while it runs on your huge numbers;-).

Answer 2

This should be a better fit then the trivial approach for large numbers (although with this kind of number crunching every pure Python implementation will take a while): Pollard Rho prime factorization.

Answer 3

('''==============================================================================='''

   '''              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

the code works with a bit of delay on the number : "1238162376372637826" but extending it to (109026109913291424366305511581086089650628117463925776754560048454991130443047109026109913291424366305511581086089650628117463925776754560048454991130443047) makes python go crazy. Is there any way just like above, i can have it calculated it in no time.

Answer 4

For a Python-based solution, you might want to look at pyecm On a system with gmpy installed also, pyecm found the following factors:

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

There still is a 98 digit unfactored composite:

60252507174568243758911151187828438446814447653986842279796823262165159406500174226172705680274911

Factoring this remaining composite using ECM may not be practical.

Edit: After a few hours, the remaining factors are

6060517860310398033985611921721

and

9941808367425935774306988776021629111399536914790551022447994642391