integer square roots

Paul Rubin http
Thu Jul 23 20:35:27 EDT 2009

timro21 <timro21 at> 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. has some advice about how to do

sci.crypt might be another good place to ask this question.

More information about the Python-list mailing list