Sat Aug 7 20:25:32 CEST 2010
( From conversation with Antti; looking up some background
Exactly half of the integers in range [1..(p-1)] are quadratic
residues (QR), and the other half are non-residues of prime p.
q is QR if there exists a x : x^2 = q (mod p)
In other words, x is the square root of q in the field Z/pZ.
I.e. for p = 5.
1^2 = 1
2^2 = 4
3^2 = 4 (9)
4^2 = 1 (16)
Meaning 1 and 4 are QRs and 2 and 3 are not.
Why is this? Each number can be written as g^n, where g is a
generator of the cyclic multiplicative group of the field Z/pZ.
If n is even, g^n has a square root as g^(n/2).
With the exception of p-2, exactly half of the elements of the field
Z/pZ has a square root, as there are always an even number of elements
in the multiplicative group, which has order p-1.