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. <br>
<br>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.<br><br>Hope it helps.<br>
<br>Regards<br>Taskinoor Hasan (Sajid)<br><br><div class="gmail_quote">On Mon, Mar 8, 2010 at 1:15 PM, Fahad Ahmad <span dir="ltr"><<a href="mailto:miraclesoul@hotmail.com">miraclesoul@hotmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div>
Thanks Geremy,<br><br>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..........<br>superb i would say.<br><br>lastly, i am using the code below to calculate Largest Prime factor of a number:<br>
<br>print ('''==============================================================================='''<br> ''' CALCULATE HIGHEST PRIME FACTOR '''<br>
'''===============================================================================''')<br><br>#!/usr/bin/env python<br>def highest_prime_factor(n):<br> if isprime(n):<br> return n<br>
for x in xrange(2,n ** 0.5 + 1):<br> if not n % x:<br> return highest_prime_factor(n/x)<br>def isprime(n):<br> for x in xrange(2,n ** 0.5 + 1):<br> if not n % x:<br> return False<br> return True<br>
if __name__ == "__main__":<br> import time<br> start = time.time()<br> print highest_prime_factor(1238162376372637826)<br> print time.time() - start<br><br>the code works with a bit of delay on the number : "1238162376372637826" but extending it to (109026109913291424366305511581086089650628117463925776754560048454991130443047109026109913291424366305511581086089650628117463925776754560048454991130443047)<br>
makes python go crazy. Is there any way just like above, i can have it calculated it in no time.<br><br><br>thanks for the support.<br><br><br><br><br>> Date: Sun, 7 Mar 2010 15:40:59 -0500<br>> Subject: Re: Calculating very large exponents in python<br>
> From: <a href="mailto:debatem1@gmail.com" target="_blank">debatem1@gmail.com</a><br>> To: <a href="mailto:miraclesoul@hotmail.com" target="_blank">miraclesoul@hotmail.com</a><br>> CC: <a href="mailto:python-list@python.org" target="_blank">python-list@python.org</a><div>
<div></div><div class="h5"><br>> <br>> On Sun, Mar 7, 2010 at 1:55 PM, Fahad Ahmad <<a href="mailto:miraclesoul@hotmail.com" target="_blank">miraclesoul@hotmail.com</a>> wrote:<br>> > Dear All,<br>> ><br>
> > i am writing my crytographic scheme in python, i am just a new user to it.<br>> > I have written the complete code, the only point i am stuck it is that i am<br>> > using 256 exponentiation which is normal in crytography but python just<br>
> > hangs on it.<br>> ><br>> > g**x [where both g and x are 256 bit numbers , in decimal they are around<br>> > 77]<br>> ><br>> > after reading several forums, i just come to know it can be done using<br>
> > numpy, i have installed python(x,y) has has both numpy and scipy installed<br>> > but i am not able to make it happen.<br>> ><br>> > any idea which library, module, or piece of code can solve this mystery :S<br>
> ><br>> > sorry for bad english<br>> <br>> A couple of things:<br>> <br>> 1) if you're working with modular exponentiation, remember that pow() takes<br>> three arguments, ie:<br>> <br>> a = 222222222222222222222222222<br>
> b = 5555555555555555555555555555<br>> pow(a, b, 1200)<br>> <br>> will calculate the correct answer (768) very quickly, while<br>> <br>> a**b % 1200<br>> <br>> has not terminated in the time it took me to compose this<br>
> email.<br>> <br>> 2) sage has a lot of excellent tools for crypto/cryptanalysis that you<br>> may want to take a look at.<br>> <br>> 3) not saying you don't know what you're doing, but be careful when<br>
> rolling your own cryptosystems- even very good cryptographers make<br>> implementation mistakes!<br>> <br>> Geremy Condra<br> <br></div></div><div class="hm"><hr>Hotmail: Powerful Free email with security by Microsoft. <a href="http://clk.atdmt.com/GBL/go/201469230/direct/01/" target="_blank">Get it now.</a></div>
</div>
<br>--<br>
<a href="http://mail.python.org/mailman/listinfo/python-list" target="_blank">http://mail.python.org/mailman/listinfo/python-list</a><br>
<br></blockquote></div><br>