This is a sequel to last week’s blog post “Two applications of finite fields to computational number theory“. The main reason I decided to write a follow-up is that I’ve learned a lot about Concluding Observations #1 and #6 from that post during the last week. In Observation #1, I mentioned without further comment a recursive procedure for computing square roots modulo a prime; it turns out that this procedure is essentially equivalent to Cipolla’s algorithm, but was discovered independently by Lehmer (who it seems did not know about Cipolla’s work). I learned this from the wonderful book “Édouard Lucas and Primality Testing” by Hugh C. Williams, which I highly recommend to anyone interested in the history of mathematics. In explaining the connection between the algorithms of Cipolla and Lehmer, I’ll make a digression into the general theory of Lucas sequences, which I had some vague knowledge of before but which I’ve learned a lot about in the last week from reading Williams’ book. In Observation #6, I asked if there was a conceptual explanation for the fact that the Chebyshev polynomial shows up in the Lucas-Lehmer test; Greg Kuperberg sent me just such an explanation and I will expand on his comments below.
Note: In this post I will assume more background in abstract algebra than in the last post.
Lucas and primality testing
On this web page, Williams writes: “[In the book] I show the tremendous influence on primality testing wielded by Édouard Lucas, the first individual to show that primality testing could be performed, at least on certain forms of numbers, without recourse to the laborious and tedious process of trial division.”
One of Lucas’ wonderful discoveries was that the Fibonacci sequence defined by and for has a natural “companion sequence” (the Lucas sequence) defined by , and for . The relationship between the sequences and is, roughly speaking, like the relationship between sine and cosine. For example, we have (*) (similar to the formula ) and (**) . Lucas discovered the sequence in connection with primality testing. In fact, he showed that the 39-digit Mersenne number is prime using roughly the following argument.
First all, by examining the factorizations of various Fibonacci numbers, Lucas noticed that if is a prime divisor of such that for all proper divisors of (such a prime is called a primitive prime divisor of ), then . (For example, 17 is a primitive prime divisor of and a non-primitive prime divisor of .) Formulas (*) and (**) readily imply that if is an odd prime and , then is a primitive prime divisor of and hence . Thus to show that is prime, it suffices to show that (apply the previous sentence to a prime dividing ). This is what Lucas actually did — but how? Lucas noticed that if we set then and for ; thus he needed to show that . This requires performing about 120 squaring operations and 120 divisions with numbers of up to 39 digits. As Williams writes in Section 3.2: “This is a lot of work by hand, but Lucas’ solution to this problem is very characteristic of him; he made the performance of this tedious arithmetic into something like a game. He said he used a chessboard to effect the computations.” Lucas would encode the squaring procedure in binary on the chessboard, with pawns in squares representing 1 and empty squares representing 0. He would take pawns away and move them around according to a specific procedure until the only pawns remaining were in the first row, and then the first row would give the least residue of modulo in binary. In the end, Lucas proved in this way that is prime without ever writing anything down!
General Lucas sequences and fast computation
Lucas considerably generalized the companion relationship between and as follows. Let be nonzero integers, and let be the two complex roots of the quadratic polynomial . Define two sequences by and . Then satisfy the recurrence relations and and and . The sequences and satisfy an enormous number of relations reminiscent of trigonometric identities. For example, we have where and . We also have the important duplication formulas and .
By combining the recurrence relations and duplication formulas, it is possible to compute and in additions and multiplications. This is something that Lehmer knew, but oddly there is no evidence that Lucas was aware of this. The idea is as follows: we write in binary and begin with the ordered pair . Moving from left to right in the binary representation of , given we compute either (if the bit is a 0) or (if the bit is a 1). This process will terminate with the ordered pair . (To compute we use the formula , which follows from the recurrence relation and duplication formulas.) One can then compute as . These computations can of course all be done modulo if that is all we care about.
As a special case, this gives a fast way to compute the Fibonacci number (note that with the parameters and ). For example, to compute we write 11 in binary as and then use the formulas and to successively compute .
We can consider (generalized) Lucas sequences made up of polynomials as well as integers. A particularly interesting choice is to take and . The corresponding sequence of polynomials is denoted and is denoted . These are referred to as Chebyshev polynomials (of the second and first kind, respectively, and normalized to be monic). For example, we have and , and and . The polynomial satisfies the important identity , from which one deduces that if lies on the complex unit circle (so that , then . In other words, we have . Thus the group homomorphism on the unit circle becomes after applying the transformation . Similarly, we have .
The Cipolla-Lehmer algorithm for modular square roots
Let be an odd prime and let be a quadratic residue modulo . We will explain an efficient (but not provably polynomial-time) algorithm for computing the two square roots of modulo using Lucas sequences. It is a minor modification of an algorithm due to Lehmer (cf. Studies in Number Theory, ed. by W. J. LeVeque, Prentice-Hall 1969) which is more or less equivalent to Cipolla’s algorithm.
As in Cipolla’s algorithm, the first step is to find an integer such that is a quadratic non-residue modulo . Let be the finite field of order , and let be a square root of in . By Cipolla’s theorem, belongs to the prime subfield of and is a square root of . (Indeed, by Galois theory we have for all , so .) By the theory of Lucas sequences, if we set and then in , where and . It follows that is a square root of modulo . Indeed, since belongs to and , we have and so . Thus the quantity in Cipolla’s square root formula is equal to . We therefore obtain:
Cipolla-Lehmer algorithm: Compute such that is a quadratic non-residue modulo . Define a sequence of integers modulo by and . Compute using the efficient procedure described above. Then the square roots of modulo are .
The Lucas-Lehmer test and the Chebyshev polynomial
We now present a modified version of Greg Kuperberg’s proof of the Lucas-Lehmer test which highlights the connection with the Chebyshev polynomial . We recall the statement of the Lucas-Lehmer test: Let be a Mersenne number. Then is prime if and only if , where denotes the iterate of .
To prove this, first suppose that is prime. By quadratic reciprocity, 2 is a quadratic residue mod and 3 is not. Let be the finite field with elements (which we can write concretely as ), and denote the non-trivial automorphism of by . Then the “circle group” is cyclic of order , since it’s the kernel of the norm homomorphism from the cyclic group to , which is known to be surjective. (We will only need the fact that is a cyclic group of order dividing , which is slightly easier to see since for , and is a subgroup of a cyclic group and is therefore cyclic.)
We claim that is a generator of the cyclic group . Since is a power of 2, this is equivalent to saying that is not a square in . Suppose for the sake of contradiction that we had for some . By the properties of Chebyshev polynomials discussed above, the map transforms the squaring map on to the map on . Thus , where . This implies that 6 is a quadratic residue mod , a contradiction (since 2 is a residue and 3 is a non-residue).
Thus but in . Applying the transformation (note that for ), the first condition implies that in . Since iff and iff , it follows from the second condition that . Since iff , we obtain in as desired.
Now suppose that and let be a prime dividing . Let , and let . Then there is a natural surjective homomorphism , and is isomorphic to either or , depending on whether or not 3 is a square modulo . Projecting onto the first factor in the former case, we obtain a surjective homomorphism where is either or .
We claim that the image in of has order . Given the claim, it follows that divides either or , and in any case . Since this is true for all prime divisors of , we conclude that is prime.
To prove the claim, we essentially reverse the argument above. Since in , and hence in , it follows that and in . Thus and . If in then , a contradiction. Thus has order in as claimed.
1. For the record, Lehmer’s proof of correctness for the Cipolla-Lucas algorithm is slightly different from ours and goes as follows. Let be the complementary Lucas sequence modulo and note that , so either or . The relation together with Euler’s criterion shows that , since is a quadratic non-residue mod . Thus and as desired.
2. The ring denoted in this earlier post is isomorphic to the ring considered above.
3. Our Chebyshev polynomials are related to the usual Chebyshev polynomials (as defined here, for example) via the conjugation relation . The Chebyshev polynomials have many important properties; for example, they form a family of orthogonal polynomials and has the minimal -norm (maximal absolute value) on among all monic polynomials of degree with real coefficients (and is the unique minimizer).
4. As mentioned above, Lucas was interested in primitive prime divisors of the Fibonacci sequence. Carmichael (who studied Lucas’s work carefully but was also quite critical of it) proved that has a primitive prime divisor for all . Much later, Schinzel proved that all sufficiently large terms in any Lucas sequence have primitive prime divisors.