CODEWITHSUNDEEP
pythonprimesfactorization
miraclesoul
miraclesoul

Reputation: 33

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

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?

Upvotes: 1

Views: 10434

Answers (4)

miraclesoul
miraclesoul

Reputation: 33

('''==============================================================================='''
>        '''              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.

Upvotes: -1

casevh
casevh

Reputation: 11404

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

Upvotes: 3

ChristopheD
ChristopheD

Reputation: 116157

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.

Upvotes: 2

Alex Martelli
Alex Martelli

Reputation: 881685

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;-).

Upvotes: 1

Related Questions