Calculating very large exponents in python

[casevh]

[also replying to Geremy since the OP's message doesn't appear...]

On Mar 8, 11:05 am, geremy condra <debat... at gmail.com> wrote:
> On Mon, Mar 8, 2010 at 2:15 AM, Fahad Ahmad <miracles... 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
> > (10902610991329142436630551158108608965062811746392577675456004845499113044­304710902610991329142436630551158108608965062811746392577675456004845499113­0443047)
> >  makes python go crazy. Is there any way just like above, i can have it
> > calculated it in no time.
>
> > thanks for the support.
>
> If you're just looking for the largest prime factor I would suggest using
> a fermat factorization attack. In the example you gave, it returns
> nearly immediately.
>
> Geremy Condra- Hide quoted text -
>
> - Show quoted text -

For a Python-based solution, you might want to look at pyecm (http://
sourceforge.net/projects/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.

casevh