[<<][math][>>][..]

Sat Aug 7 20:25:32 CEST 2010

Quadratic Residues

( From conversation with Antti; looking up some background
information.. )

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.

[1] http://en.wikipedia.org/wiki/Quadratic_residue

[Reply][About]

[<<][math][>>][..]