geremy condra
3/8/2010 7:09:00 PM
On Mon, Mar 8, 2010 at 2:05 PM, geremy condra <debatem1@gmail.com> wrote:
> On Mon, Mar 8, 2010 at 2:15 AM, Fahad Ahmad <miraclesoul@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