integer square roots
Paul Rubin
http
Thu Jul 23 20:35:27 EDT 2009
timro21 <timro21 at gmail.com> writes:
> I wish to process billions of 100-digit numbers and test if each has
> an integer square root. What's the most efficient way to do this?
Is this a homework problem? If not, may I ask what the application is?
I think the basic answer is 1) use the law of quadratic reciprocity to
eliminate a lot of the inputs quickly (for example, just looking at
the low 8 bits of an input number should eliminate about 5/6th of
them); 2) use GMP and Newton's method to check the rest.
http://cr.yp.to/papers/powers.pdf has some advice about how to do
that.
sci.crypt might be another good place to ask this question.
More information about the Python-list
mailing list