integer square roots

[Paul Rubin]

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.