Detecting Squares

What is the most efficient method for determining whether a given
integer N is a perfect square?  One approach would be to check to 
see if N is a square modulo several small numbers, which can probably 
be done more easily than extracting the full square root.  For 
example, if we want to find out whether the number

              N = 371930958274059827465211239444089

is a square, we can first check the last two decimal digits to see
if they are one of the twenty-two possible squares (mod 100), ten of
which are obvious {00,01,04,09,..,81} and the remaining twelve of
which are {21,24,29,41,44,56,61,69,76,84,89,96}.  The chances of a
randomly selected non-square integer passing this test is just 22/100.

Then, taking advantage of the fact that 999999 = 3*3*7*11*13*37, we
can check to see if N is a square modulo each of these primes by
simply forming the sum of the digits of N taken 6 at a time:

                            444089
                            211239
                            827465
                            274059
                            930958
                               371
                           -------
                     SUM = 2688181

The squares (mod 9) are {0,1,4,7}, and this SUM is congruent to 
7 (mod 9), so we still can't be sure it's non-square.  However, it 
is congruent to 6 (mod 7), whereas the squares (mod 7) are {0,1,2,4},
so N can't be a square.  

In general, I'd expect the probability of a randomly chosen non-square
integer passing the "squareness test" relative to (2^2)(5^2), 3^2, 7,
11, 13, and 37 to be about

                22    4    4    6     7     19
           P = ----  ---  ---  ----  ----  ----  =  0.0084
               100    9    7    11    13    37

so it will catch over 99% of the non-squares.

Or, we could take advantage of the fact that 1001=7*11*13 and so 
1000 = -1 (mod 7*11*13).  Thus, if we take the digits of N in groups
of 3, and alternately add and subtract them, we can easily check for
squareness modulo 7, 11, and 13.  

So the quickest approach might be to first check the last two decimal
digits for squareness (mod 100), then add up the digits one at a time
and check the sum for squareness (mod 9), and then add up the digits
three at a time (with alternating signs) and check the sum for
squareness modulo 7, 11, and 13.  This will catch over 98% of
non-squares.