MAPPING THE DISCRETE LOGARITHM
an Undergraduate Research Project,
funded by National Science Foundation REU grant
DMS-0352940

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:

• Under what circumstances can we find a "fixed point" for the DLP?  How often do they occur?  (Partially solved, but not completely.)
  
  
• Under what circumstances can we find a "two cycle" for the DLP?  How often do they occur?  (Much evidence, but little proof.)
  
  
• What should a "random" functional graph look like?  In particular, what do we expect the average values of statistics associated with the graph to be?  (Known for some sorts of statistics (number of connected components, number of cyclic nodes, number of terminal nodes, average cycle length, maximum cycle length, average tail length, and maximum tail length) and some sorts of functional graphs (unary, binary).  Lots left unknown.)
  
  
• What do we expect the standard deviation of statistics associated with a "random" functional graph to be?  (Very little known, but the methods are out there.)
  
  
• How closely do the functional graphs for the DLP resemble "random" functional graphs?  (Some data collected, but more would help.)
  
  
• What if the modulus of the discrete logarithm is composite?  (For example, prime powers or RSA numbers: n = pq where p and q are prime.)
  
  
• What about discrete logarithms in finite fields?
  
  
• What about discrete logarithms on elliptic curves (or other groups)?

• Daniel R. Cloutier.  Mapping the discrete logarithm. Senior thesis, Rose-Hulman Institute of Technology, 2005.
  

  • Code from "Mapping the Discrete Logarithm"

• Daniel R. Cloutier and Joshua Holden.  Mapping the discrete logarithm.  Preprint.
  

• Philippe Flajolet and Andrew Odlyzko. Random Mapping Statistics. In Advances in Cryptology, Proc. Eurocrypt'89, , J-J. Quisquater Ed., Lect. Notes in Comp. Sc. vol 434, 1990, pp. 329-354.
  
  
• Philippe Flajolet and Andrew Odlyzko.  Singularity analysis of generating functions.  In SIAM J. Discrete Math., vol 3 (1990) pp. 216-240.
  
  
• Philippe Flajolet and Andrew Odlyzko.  The Average Height of Binary Trees and Other Simple Trees. In Journal of Computer and System Scienes, vol 25, 1982, pp. 171-213.
  
  
• P. Flajolet, Z. Gao, A. Odlyzko, and B. Richmond . The distribution of heights of binary trees and other simple trees (44kb).  In Combinatorics, Probability, and Computing, vol 2 (1993), pp. 145-156.
  
  
• Joshua Holden.  Fixed Points and Two-Cycles of the Discrete Logarithm. In: Algorithmic number theory: 5th international symposium; proceedings, no. 2369 in Springer Lecture Notes in Computer Science, Springer-Verlag, 2002.
  
  
• Joshua Holden. Distribution of the Error in Estimated Numbers of Fixed Points of the Discrete Logarithm. Communications in Computer Algebra, 38:111–118, 2004.
  
  
• Joshua Holden and Pieter Moree.  New Conjectures and Results for Small Cycles of the Discrete Logarithm.  In: High Primes and Misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams, no. 41 in Fields Institute Communications, AMS, 2004.
  
  
• Joshua Holden and Pieter Moree. Some heuristics and results for small cycles of the discrete logarithm. Mathematics of Computation, 75:419--449, 2006.
  
  

• Information about the "Theorodrome" computers. (The Linux machines in the classrooms we are using.)
  
  
• Information about the RHIT parallel cluster.
  
  
• Information about the beamer package for latex and about presentations in general.
  
  
• The Algolib package for Maple and lots of tutorials and other information
  
  
• The GraphTheory package for Maple
  
  
• The On-Line Encyclopedia of Integer Sequences
  
  
• Mapping the Discrete Logarithm talk notes

• Max F. Brugger and Christina A. Frederick. The Discrete Logarithm Problem and Ternary Functional Graphs.  Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 8, Issue 2, 2007.
  
  
• Matthew Niemerg. Isomorphisms of Elliptic Curves over Extensions of Finite Fields.
  
  
• Philip Brunetti. Structural Properties of the Mapping g^x → g^x2. (Draft)