Calculating very large exponents in python

[Fahad Ahmad]

Thanks Geremy,

That has been an absolute bump........... GOD i cant sit on my chair, it has worked even on 512 bit number and with no time..........
superb i would say.

lastly, i am using the code below to calculate Largest Prime factor of a number:

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


thanks for the support.




> Date: Sun, 7 Mar 2010 15:40:59 -0500
> Subject: Re: Calculating very large exponents in python
> From: debatem1 at gmail.com
> To: miraclesoul at hotmail.com
> CC: python-list at python.org
> 
> On Sun, Mar 7, 2010 at 1:55 PM, Fahad Ahmad <miraclesoul at hotmail.com> wrote:
> > Dear All,
> >
> > i am writing my crytographic scheme in python, i am just a new user to it.
> > I have written the complete code, the only point i am stuck it is that i am
> > using 256 exponentiation which is normal in crytography but python just
> > hangs on it.
> >
> > g**x  [where both g and x are 256 bit numbers , in decimal they are around
> > 77]
> >
> > after reading several forums, i just come to know it can be done using
> > numpy, i have installed python(x,y) has has both numpy and scipy installed
> > but i am not able to make it happen.
> >
> > any idea which library, module, or piece of code can solve this mystery :S
> >
> > sorry for bad english
> 
> A couple of things:
> 
> 1) if you're working with modular exponentiation, remember that pow() takes
> three arguments, ie:
> 
> a = 222222222222222222222222222
> b = 5555555555555555555555555555
> pow(a, b, 1200)
> 
> will calculate the correct answer (768) very quickly, while
> 
> a**b % 1200
> 
> has not terminated in the time it took me to compose this
> email.
> 
> 2) sage has a lot of excellent tools for crypto/cryptanalysis that you
> may want to take a look at.
> 
> 3) not saying you don't know what you're doing, but be careful when
> rolling your own cryptosystems- even very good cryptographers make
> implementation mistakes!
> 
> Geremy Condra
 		 	   		  
_________________________________________________________________
Hotmail: Powerful Free email with security by Microsoft.
http://clk.atdmt.com/GBL/go/201469230/direct/01/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20100308/07e95753/attachment-0001.html>