... pretty unobvious. Apart from just reading it, here's a concrete toy example: Imagine p=11 (so the "ring of integers" here is basically integers mod 11 with addition and multiplication defined), so q=5.

Now some numbers mod 11 are "quadratic residues" (means: squares) and some are not.

It's pretty obvious that ~ 1/2 are squares, because mod p, (p-x)^2 = p^2 -2px +x^2 = x^2 mod p. But that doesn't tell you *which* half are squares.

(2/n)

waxwing@waxwing@x0f.orgAs the author observes, the ones that *are* squares form a multiplicative group of order 5 (i.e. p-1/2), and that is exactly the group he needs to satisfy the properties of El Gamal's encryption scheme. He knows he has q numbers to work with, but it is *not* 0 ... q-1 (so 0..4 in our toy example), it is the q numbers in that group, so he has to map from Zq to Gq, as he puts it.

It turns out the Legendre symbol gives him exactly what he needs to do that.