Lucas sequences and Chebyshev polynomials

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.   LucasBookIn 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 x^2 - 2 shows up in the Lucas-Lehmer test; Greg Kuperberg sent me just such an explanation and I will expand on his comments below. Continue reading

Two applications of finite fields to computational number theory

In this post I’d like to discuss how finite fields (and more generally finite rings) can be used to study two fundamental computational problems in number theory: computing square roots modulo a prime and proving primality for Mersenne numbers.  The corresponding algorithms (Cipolla’s algorithm and the Lucas-Lehmer test) are often omitted from undergraduate-level number theory courses because they appear, at first glance, to be relatively sophisticated.  This is a shame because these algorithms are really marvelous — not to mention useful — and I think they’re more accessible than most people realize. I’ll attempt to describe these two algorithms assuming only a standard first-semester course in elementary number theory and familiarity with complex numbers, without assuming any background in abstract algebra.  These algorithms could also be used in a first-semester abstract algebra course to help motivate the practical utility of concepts like rings and fields.

Anecdotal Prelude

In researching this blog post on Wikipedia, I learned a couple of interesting historical tidbits that I’d like to share before getting on with the math.

elucasThe French mathematician Edouard Lucas (of Lucas sequence fame) showed in 1876 that the 39-digit Mersenne number 2^{127}-1 is prime.  This stood for 75 years as the largest known prime.  Lucas also invented (or at least popularized) the Tower of Hanoi puzzle and published the first description of the Dots and Boxes game.  He died in quite an unusual way: apparently a waiter at a banquet dropped what he was carrying and a piece of broken plate cut Lucas on the cheek. Lucas developed a severe skin inflammation and died a few days later at age 47.

Derrick Henry Lehmer was a long-time professor of mathematics at U.C. Berkeley.  In 1950, Lehmer was one DHLehmerof 31 University of California faculty members fired for refusing to sign a loyalty oath during the McCarthy era.  In 1952, the California Supreme Court declared the oath unconstitutional, and Lehmer returned to Berkeley shortly thereafter.  Lehmer also built a number of fascinating mechanical sieve machines designed to factor large numbers. Continue reading