Primitive roots, discrete logarithms, and p-adic numbers

hellmanThis morning I attended Martin Hellman’s stimulating keynote address at the 2013 Georgia Tech Cyber Security Summit. Martin Hellman is the co-inventor, with Whitfield Diffie, of the Diffie-Hellman Key Exchange Protocol, which began the (public) public-key cryptography revolution.  Among the interesting things I learned during Martin Hellman’s talk are:

1. Hellman feels that Ralph Merkle deserves equal credit for inventing public-key cryptography and refers to his own invention as the Diffie-Hellman-Merkle key exchange protocol.  (Merkle was the director of the Georgia Tech Information Security Center from 2003-2006.)

2. Hellman came up with the famous “double padlock” thought experiment after the invention of the Diffie-Hellman-Merkle key exchange protocol, as a way to explain it to others.  The mathematics came first.  (I had always wondered about this.)

gill3. Most interestingly, Hellman said that he got the idea to use modular exponentiation/discrete logarithms as a “one-way function” from the engineer and mathematician John Gill (who I never heard of before this morning).  John Gill’s other suggestion was to use multiplication/factoring, which forms the basis of RSA!  It’s all the more amazing that I’ve never heard of John Gill because he earned his bachelor’s degree in Applied Mathematics from Georgia Tech (where I now teach) and his Ph.D. in Mathematics from U.C. Berkeley (where I got my Ph.D.)!  Hellman also recounted a conversation in which Gill (who is African-American) mentioned having encountered very little racial intolerance during his undergraduate studies in the 1960’s — apparently Georgia Tech was (relatively speaking) an oasis of tolerance among southern universities during that time.

Now on to the mathematical part of this post, which is an unusual proof of the existence of primitive roots modulo primes which I came up with recently while preparing a lecture for my course on Number Theory and Cryptography.  The proof is much less elementary than every other proof I’ve seen, but I would argue that it nevertheless has some merit.   I have always been intrigued by the fact that it is difficult to find primitive roots modulo a large prime p, and also by the fact that there is no known way to efficiently compute an isomorphism ({\mathbf Z}/p{\mathbf Z})^* \to {\mathbf Z}/(p-1){\mathbf Z} even when a primitive root is known.  The usual elementary proofs of the fact that ({\mathbf Z}/p{\mathbf Z})^* is cyclic do not directly construct an isomorphism with {\mathbf Z}/(p-1){\mathbf Z}; instead, one assumes that every element of ({\mathbf Z}/p{\mathbf Z})^* has order smaller than p-1 and derives a contradiction by some counting argument.  One can in fact construct an isomorphism ({\mathbf Z}/p{\mathbf Z})^* \to {\mathbf Z}/(p-1){\mathbf Z} in a very natural (but somewhat unusual) way as follows.

By Fermat’s Little Theorem and the fact that a polynomial of degree d over a field can have at most d roots, the polynomial f(x) = x^{p-1} - 1 \in {\mathbf Z}[x] has p-1 distinct roots modulo p.  By Hensel’s Lemma, f(x) therefore has p-1 distinct roots in the ring {\mathbf Z}_p of p-adic integers.  The set H of roots of f(x) in {\mathbf Z}_p forms a (multiplicative) group, and reduction modulo p gives a  isomorphism from H to ({\mathbf Z}/p{\mathbf Z})^* whose inverse ({\mathbf Z}/p{\mathbf Z})^* \to H is usually called the “Teichmuller lift”.  We view H as the group of (p-1)^{\rm st} roots of unity in the field {\mathbf Q}_p of p-adic numbers.  The subfield K = {\mathbf Q}(H) of {\mathbf Q}_p is a splitting field for f(x) over {\mathbf Q}.  Let \mu_{p-1} denote the group of (p-1)^{\rm st} roots of unity in the field {\mathbf C} of complex numbers.  Then the subfield L = {\mathbf Q}(\mu_{p-1}) of {\mathbf C} is also a splitting field for f(x) over {\mathbf Q}.  By the uniqueness of splitting fields, there is an isomorphism from K to L, which necessarily induces an isomorphism of multiplicative groups H \to \mu_{p-1}.  The complex logarithm (or more precisely, the inverse of the map {\mathbf Z}/(p-1){\mathbf Z} \to \mu_{p-1} given by z \mapsto e^{2 \pi i z / (p-1)}) gives an isomorphism \mu_{p-1} \to {\mathbf Z}/(p-1){\mathbf Z}.  Composing the isomorphisms ({\mathbf Z}/p{\mathbf Z})^* \to H, H \to \mu_{p-1}, and \mu_{p-1} \to {\mathbf Z}/(p-1){\mathbf Z} gives the desired isomorphism ({\mathbf Z}/p{\mathbf Z})^* \to {\mathbf Z}/(p-1){\mathbf Z}.

Of course, the isomorphism which we just constructed is not really explicit, since it invoked the uniqueness of splitting fields as a black box.  But this is really the only non-explicit step, and the only one which is not efficiently computable (Hensel’s Lemma is proved by p-adic Newton iteration, which as in the classical case is efficient).   So the hardness of the Discrete Logarithm Problem (on which the Diffie-Hellman-Merkle key exchange protocol is based) is intimately related to the non-explicit nature of the fact that any two splitting fields are isomorphic!

Rhetorical question: Can one turn the above proof into an algorithm for computing discrete logarithms?  Normally I would be highly skeptical, but today Martin Hellman has inspired me to be an optimist!

The existence of primitive roots modulo p^k (where p is an odd prime and k is a positive integer), assuming the result for k=1, can also be proved by a rather non-elementary argument using basic properties of the p-adic exponential and logarithm maps.  I haven’t seen this written down before, but I assume that it must be known to many experts.  Anyway, here is a sketch of the argument.  The p-adic logarithm map \log_p(1+x) = \sum_{n=1}^\infty \frac{(-1)^{n+1} x^n}{n} converges for all x \in {\mathbf Z}_p satisfying |x|_p < 1.  Similarly, the p-adic exponential map \exp_p(x) = \sum_{n=0}^\infty \frac{x^n}{n!} converges for all x \in {\mathbf Z}_p satisfying |x|_p < p^{-1/(p-1)}.  When defined, these functions are inverse to each other.  These two maps furnish a group isomorphism (1+p{\mathbf Z}_p, \cdot) \cong (p {\mathbf Z}_p, +).  By the Hensel’s Lemma argument above, there is a group isomorphism {\mathbf Z}_p^* \cong H \times (1+p{\mathbf Z}_p), where H is the group of (p-1)^{\rm st} roots of unity in {\mathbf Z}_p.  Reducing both sides of the isomorphism {\mathbf Z}_p^* \cong H \times p {\mathbf Z}_p modulo p^k gives an isomorphism ({\mathbf Z}/p^k {\mathbf Z})^* \cong ({\mathbf Z}/ p{\mathbf Z})^* \times {\mathbf Z}/p^{k-1}{\mathbf Z}.  Since we already know that ({\mathbf Z}/p{\mathbf Z})^* is cyclic of order p-1, the Chinese Remainder Theorem implies that ({\mathbf Z}/p^k{\mathbf Z})^* \cong {\mathbf Z}/(p-1)p^{k-1}{\mathbf Z} as desired.

When p=2, the above argument does not quite work but the p-adic exponential and logarithm maps still define an isomorphism (1+p^2{\mathbf Z}_p, \cdot) \cong (p^2 {\mathbf Z}_p, +).  The above argument can then be modified to show that ({\mathbf Z}/2^k{\mathbf Z})^* \cong {\mathbf Z}/2{\mathbf Z} \times {\mathbf Z}/2^{k-2}{\mathbf Z} for k \geq 2.

Concluding observations:

1. More information about the history of public key cryptography, including a mention of John Gill’s role, can be found here.

2. The reader will find six elementary proofs of the fact that ({\mathbf Z}/p{\mathbf Z})^* is cyclic in this expository paper by Keith Conrad.

3. The unusual interplay between p-adic and complex analysis in the first argument above is reminiscent of the more sophisticated arguments which Laura DeMarco and I use in this paper to prove the following result in complex dynamics: if a,b are complex numbers with a \neq \pm b, then there are only finitely many complex numbers c such that a and b both have finite orbit under iteration of the polynomial map z^2 + c.  (See the overview of the proof in Section 1.3 of our paper.)

4. My Ph.D. student Andrew Dudzik worked out a more elementary version of the second argument above in which one works throughout with truncations of the p-adic logarithm and exponential maps as polynomials in {\mathbf Z} / p^k {\mathbf Z} [x] and never needs to mention p-adic numbers at all.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s