an Undergraduate Research Project,
funded by National Science Foundation REU grants
DMS-0352940, DMS-1003924

Functional Graph of a Discrete Exponentiation Map

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 determine this would be to construct the "functional graph" associated with the transformation. Any unexpected characteristics of this functional graph might lead to new progress in breaking the discrete logarithm problem.

Open questions to explore regarding this functional graph include:

2011 Possible Project List (revised 8 Jun 2011)

Mapping the Discrete Logarithm talk notes:
Some references (more available on request):

Reports from the 2007 REU:
Reports from the 2009 REU:
Reports from the 2010 REU:
Reports from the 2011 REU:

Reports from the 2014 Mini-REU at Mount Holyoke College:

Other resources: