All the coded messages were the first lines of famous poems:
(0) d=7961: Shall I compare thee to a summer's day? (A sonnet of Shakespeare)
(1) d=8181: Much have I travelled in the realms of gold (On first looking into Chapman's Homer, John Keats)
(2) d=1901: Yet once more O ye laurels and once more (Lycidas, John Milton)
(3) d=6323: Had we but world enough and time (To his coy mistress, Andrew Marvell)
(4) d=921: We are as clouds that veil the midnight moon (Mutability, Percy Bysshe Shelley)
I realized afterward that I had missed a perfect first line for this exercise, from Ode to Psyche by John Keats: "O Goddess, hear these tuneless numbers wrung / By sweet enforcement and remembrance dear / And pardon that thy secrets should be sung / Even into thine own soft-conched ear!"
The reason that public key codes can exist at all is that some computations are fast to carry out -- like the ones used in encryption and normal decryption -- while others are so slow to carry out that they are in effect impossible, in this case the computations that would break the code. Here is a table making this distinction:
| FAST COMPUTATIONS | SLOW COMPUTATIONS |
| Multiplication | Factoring |
| Raising to an integer power in Zp* | Finding a generator of Zp* |
| Finding a square root in Zp*? |
The fast computations are all that you need to do encryption and decryption with the public codes. To break these codes, however, you need to factor n, and that is slow. The fast computations are fast because there is a kind of "formula" to follow. When you multiply, for example, you just take some digits, do specified operations to create other digits, and that's the answer. But slow computations are slow because there is no formula: you have to do some kind of search. When you try to factor a number, there is no formula for the factor: you just have to look for something that will work. If the set of possible answers is very large, the search could take an impossibly long time.
In all these cases there is no PROOF that the slow computation is really slow, it's just that no one has found a fast way yet, and it is conjectured that no one ever will. If someone found a fast way to factor large numbers, it would be a fantastic surprise, with enormous implications for the world economy, diplomacy, etc.
To me, one of the most surprising things about number theory is that there is no fast way to find a generator of Zp* (p a prime). We know generators exist, by the counting argument involving polynomials. Not all elements of Zp* can have order as small as (p-1)/2, and hence there exist elements with order (p-1), and these are therefore generators. But this proof gives no clue which elements the generators are. They must be searched for. In fact, there is usually a "small" generator, so that a search would turn one up quite quickly, but no one knows if this is always true.
I believe the last item in the table "Finding a square root in Zp*" requires a search, i.e., there is no formula for the square root of an element, if it even exists. Our topic today has to do with the question of existence: there IS a fast way to find out if a square root exists. It makes use of a famous result of Gauss, "quadratic reciprocity."
Here is an example to introduce the problem of squares and square roots: Find all the squares in Z7*={1,2,3,4,5,6}. If you square these elements in order, you find 1,4,2,2,4,1. That is, only {1,2,4} occur as squares. The others, {3,5,6} are non-squares. If you represent the elements in terms of a generator, like 3, you get some insight into what is going on. The squares are 2=3^2, 4=3^4, 1=3^6, i.e., 3 to an even power, while the non-squares are 3=3^1, 6=3^3, 5=3^5, i.e. 3 to an odd power. The squares have square roots of course: 1 has 1, -1=6 (mod 7) as square roots. 2 has 3, -3=4 (mod 7) as square roots. 4 has 2, -2=5 (mod 7) as square roots. This is a familiar pattern: if a is a square root of b, then -a is also.
It is easy to see that this is a general pattern. Let p be an odd prime, and represent the elements of Zp* in terms of a generator a:
The last element is of course 1, by Fermat's Little Theorem, and also by the definition of a generator (a has order p-1). Now look at what you get when you square any element:
You get an even exponent. Clearly every even exponent corresponds to an element which is a square, and and every square is represented by an even exponent. Thus exactly half of the elements of Zp* are squares, the ones with even exponents. This includes a^(p-1), since (p-1) is even, and we can check that this element is an obvious square: it is 1, and 1=1*1.
The odd exponents correspond to non-squares. We already noticed this in the Z7* example, but it is general, as we now see, for Zp*, p an odd prime.
When you multiply numbers in Zp*, you just add their exponents, if the elements are represented in terms of a generator. Adding two even exponents would give an even exponent, i.e.
Similarly, since (odd+even = odd), and (odd+odd=even), we see
This little multiplication table is just like the multiplication of {-1,1}, where (1) corresponds to (square), and (-1) corresponds to (non-square). For example (-1)*(-1)=1. That is, there is a homomorphism from Zp* onto {-1,1}, in which squares correspond to 1, and non-squares correspond to -1.
There is a somewhat unfortunate notation for the homomorphism described just above, called the Legendre symbol: it is [a/p], meaning 1 if a is a square (mod p) and -1 if a is a non-square. The unfortunate part is that it looks like a fraction. IT ISN'T! You must consciously remind yourself what it really is: [a/p] is sort of like the answer to the question "Is a a square modulo the prime p?" The answer comes back as a 1 (meaning 'yes' ) or -1 (meaning 'no').
Once one gets used to it, it is not a bad notation. Here is how the homomorphism property looks:
That is, ab is a square mod p (the left hand side is +1), if both a and b are squares (right hand side is 1*1), or if they are both non-squares (the right hand side is (-1)*(-1)). On the other hand ab is a non-square (the left hand side is -1), if exactly one of a and b is a square (the right hand side is (-1)*1, or 1*(-1)). This "multiplicative" property of the Legendre symbol is very handy in computations.
Now I am just going to assert two more properties of the Legendre symbol, without any hint of a proof! Let p be an odd prime, as usual. Then
This tells us when 2 is a square in Zp*. Sometimes it is and sometimes it isn't. It depends on p. It is a square if p is +1 or -1 mod 8. We saw an example above: 2 is a square in Z7*, as we would now fully expect, since 7 is -1 mod 8. The element 2 in Zp* is NOT a square if p is +3 or -3 mod 8. For example, 2 is NOT a square in Z11* or Z13*. (You could verify this by actually computing all the squares, and seeing that 2 does not occur.)
Finally, the most mysterious rule of all, quadratic reciprocity: It covers the case of two odd primes, p and q:
This seems to express a cooperation between odd primes p and q, as if they agreed to be both squares or both non-squares together. The cooperation breaks down, however if both primes are 3 mod 4 ( like 11 and 23) So if 11 is a square in Z23*, then 23 is NOT a square in Z11*. In fact, though, in Z11*, 23=1 (mod 11) and obviously IS a square. So it must be that 11 is NOT a square in Z23*. Again, a slow computation would verify this, but quadratic reciprocity does it fast!
These rules suffice to compute Legendre symbols, and hence to decide if elements of Zp* (p an odd prime) are squares or not. Here are some examples:
[10/37]=[2/37][5/37] (multiplicative property) = (-1)[37/5] (37=-3 mod 8; quadratic reciprocity, noting that both 37 and 5 are 1 mod 4) = (-1)[2/5] (reduce mod 5, since the Legendre symbol is asking a question in Z5*) = (-1)(-1) (2 is NOT a square in Z5*) = +1. That is, 10 IS a square in Z37*. (In fact, 11*11=10 (mod 37), and 26*26=10 (mod 37).)
[37/101]=[101/37] (quadratic reciprocity) = [27/37] (reduce mod 37) = [3/37][3/37][3/37] (multiplicative property)=[37/3][37/3][37/3] (quadratic reciprocity, noting that 37 is 1 mod 4) = [1/3][1/3][1/3] (reduce mod 3) = 1*1*1 (1 is a square in Z3*) = 1. Thus 37 is a square in Z101*. (In fact 21*21=37 (mod 101), and 80*80=37 (mod 101).)
[43/103]= - [103/43] (quadratic reciprocity, noting that both 43 and 103 are 3 mod 4, hence the minus sign) = -[17/43] (reduce mod 43) = -[43/17] (quadratic reciprocity) = -[9/17] (reduce mod 17) = -1 (note [9/17]=+1 because 9 is obviously the square of 3). Thus 43 is NOT a square in Z103*.
[52/61]=[2/61][2/61][13/61] (multiplicative property) = (-1)*(-1)*[61/13] (61 is -3 mod 8; quadratic reciprocity, noting both 61 and 13 are 1 mod 4) = [9/13] ( note (-1)*(-1)=1); reduce mod 13) = 1 (9 is a square). Thus 52 is a square mod 61. Just to verify, a tedious search reveals that 28*28=52 (mod 61). Of course then 33*33=52 (mod 61) as well, since 33=-28 (mod 61).
Find out if the following are squares, by computing the appropriate Legendre symbols. Explain your reasoning as you go:
5 mod 43
7 mod 59
24 mod 29
6 mod 37
In at least one case, verify your result by finding an explicit square root, if there is one, or by listing all the squares and showing that the given number does not turn up in the list.
HINTS: Be especially careful to use the rules appropriately. Remember that p and q are odd primes. That is the only case in which you can "flip" a Legendre symbol, by quadratic reciprocity. If you have a non-prime in the top of the symbol, use the multiplicative property to factor it down to primes. If you have a 2 in the top of the symbol, check the bottom of the symbol (mod 8). With these rules you should never get a non-prime in the bottom of the symbol.
That last case makes a good challenge problem, though! How can you decide if a is a square mod n if n is NOT a prime? I'll describe this problem a little more explicitly under Challenge Problems, but you can begin to think about it now. You could find which elements are squares in Zn*, and especially consider the homorphisms onto Zp*'s where the p's are prime factors of n.