integer square roots

[timro21]

On Jul 24, 10:35 am, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> timro21 <timr... 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.pdfhas some advice about how to do
> that.
>
> sci.crypt might be another good place to ask this question.

Homework?  Gosh no.  I have several number theory applications which
need to know (quickly) whether particular very large numbers are
perfect squares.  Since I asked this in this newsgroup I guess I
assumed that responses wuld relate specifically to how to do this
efficiently *and accurately* in Python.  Sorry if I wasn't clear.