Calculating very large exponents in python

[Taskinoor Hasan]

First of all, you simply can't use this straight approach of primality
testing for very very big numbers. There are a number of algorithms, both
deterministic and random. Please Google for them (and don't forget to check
Wikipedia too). Study the random algorithms to check whether they can be
applied in your situation, since they are faster.

And another implementation issue. Try to avoid many recursive calls. It's
always possible to convert a recursive function to a non-recursive one and
that will be faster if your recursion is too long.

Hope it helps.

Regards
Taskinoor Hasan (Sajid)

On Mon, Mar 8, 2010 at 1:15 PM, Fahad Ahmad <miraclesoul at hotmail.com> wrote:

>  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. Get it now.<http://clk.atdmt.com/GBL/go/201469230/direct/01/>
>
> --
> http://mail.python.org/mailman/listinfo/python-list
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20100308/c8fa9e04/attachment-0001.html>