Dr. Joshua Holden (2021, 2022)
Just a few decades ago, cryptography was considered a domain exclusive to national governments and militaries. However, the computer explosion has changed that. Every day, millions of people trust that their privacy will be protected as they make online purchases or communicate privately with a friend. Many of the cryptographic algorithms they use are built upon a common transformation, namely discrete exponentiation modulo an integer n. For instance, Diffie-Hellman key exchange, RSA and the Blum-Micali pseudorandom bit generator all use discrete exponentiation.
It is thought that the inverse of this transformation, the "discrete logarithm problem", or "DLP" is computationally intractable. This is part of the basis for assuming the cryptographic security of the algorithms referred to above. However, there is no known proof of this fact.
In particular, it would be interesting to know if there were patterns in this transformation that can be exploited. One way to investigate this is to look at solutions to equations modulo n=pe (where p is a prime number) involving exponential functions. Previous work has focused on solutions contained in {1, ..., pe}. Recently, we have shown that another course might also be fruitful: start with the solutions to an exponential equation which are in {1, ..., pe(p-1)} and determine how they are distributed among the subintervals of length pe. We have used p-adic methods, primarily Hensel's lemma and p-adic interpolation, to count fixed points, two-cycles, and collisions of certain exponential functions. We think the use of p-adic numbers also suggests new lines of attack that may be pursued by an REU group. For example, the ability to extend the p-adic exponential function to p-adic extension fields might provide a useful way of looking at, or even posing, new problems in finite field extensions.
Potential REU projects will consider solutions of more exponential equations based on the discrete exponentiation map and related maps. For instance, one could consider the "product exponentiation map", which is related to the ElGamal signature scheme and the Digital Signature Algorithm, and the "self-power map", which is related to variants of these algorithms. More problems that should be tractable using our methods include finding solutions of the exponential Welch equation and the Golomb equation (and their variations). These are related to "Golomb rulers", which have applications in error correction and in controlling the effects of electromagnetic signals interference.