Calculating very large exponents in python

geremy condra debatem1 at gmail.com
Mon Mar 8 20:08:48 CET 2010


On Mon, Mar 8, 2010 at 2:05 PM, geremy condra <debatem1 at gmail.com> wrote:
> 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
>

Allow me to add a very important caveat to my previous statement:
a fermat factorization is primarily useful if you know that your number
is a large semiprime, such as an RSA modulus, which I assume you
are. Otherwise, make sure and test for primality.

Geremy Con



More information about the Python-list mailing list