Calculating very large exponents in python

[geremy condra]

On Mon, Mar 8, 2010 at 2:15 AM, 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.

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