Node:Perfect Square Algorithm, Next:Perfect Power Algorithm, Previous:Nth Root Algorithm, Up:Root Extraction Algorithms
mpz_perfect_square_p is able to quickly exclude most non-squares by
checking whether the input is a quadratic residue modulo some small integers.
The first test is modulo 256 which means simply examining the least
significant byte. Only 44 different values occur as the low byte of a square,
so 82.8% of non-squares can be immediately excluded. Similar tests modulo
primes from 3 to 29 exclude 99.5% of those remaining, or if a limb is 64 bits
then primes up to 53 are used, excluding 99.99%. A single Nx1
remainder using PP from gmp-impl.h quickly gives all these
remainders.
A square root must still be taken for any value that passes the residue tests, to verify it's really a square and not one of the 0.086% (or 0.000156% for 64 bits) non-squares that get through. See Square Root Algorithm.