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

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)?
  
  
• What about other maps similar to the discrete logarithm, e.g. those involved in breaking the ElGamal signature scheme?
  

2011 Possible Project List (revised 8 Jun 2011)

• The One-Hour Version
  
  
• The Three-Hour Version (slightly older):  Part I, Part II, Part III
  
  

• General:
  
  
• The Hard Problems in Cryptography wiki Discrete Logarithms page.
  

• Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. The Handbook of Applied Cryptography, CRC Press, 1996.
  

• Comparing discrete exponentiation maps with random maps:
  

• 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.  Involve, 3:197--213, 2010.

• Nathan W. Lindle. A Statistical Look at Maps of the Discrete Logarithm. Senior thesis, Rose-Hulman Institute of Technology, 2008.
  
  
• Poster from "A Statistical Look at Maps of the Discrete Logarithm"
  
  
• Code from "A Statistical Look at Maps of the Discrete Logarithm"
  
  
• Max F. Brugger and Christina A. Frederick.  The Discrete Logarithm Problem and Ternary Functional Graphs, MSTR 07-02.  Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 8, Issue 2, 2007.
  
  
• Max F. Brugger. Exploring the Discrete Logarithm with Random Ternary Graphs. Senior thesis, Oregon State University, 2008.
  
  
• Andrew Hoffman.  Statistical Investigation of Structure in the Discrete Logarithm, MSTR 09-09.  Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 10, Issue 2, 2009.
  
  
• Code from "Statistical Investigation of Structure in the Discrete Logarithm"
  
  
• Marcus L. Mace. Discrete Logarithm over Composite Moduli, MSTR 09-07.
  
  
• Counting random maps and related objects:
  
  
• 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.
  
  
• Herbert Wilf, Generatingfunctionology, 2nd ed., Academic Press, 1994.
  
  
• Other related analyses of discrete exponentiation maps:
  
  
• 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.
  
  
• Lev Glebsky and Igor E. Shparlinski. Short Cycles in Repeated Exponentiation Modulo a Prime. Preprint.


• Jean Bourgain, Sergei V. Konyagin, and Igor E. Shparlinski. Product Sets of Rationals, Multiplicative Translates of Subgroups in Residue Rings, and Fixed Points of the Discrete Logarithm, Int Math Res Notices 2008, rnn090, 2008.


• Jean Bourgain, Sergei V. Konyagin, and Igor E. Shparlinski. Distribution on elements of cosets of small subgroups and applications, Int Math Res Notices, to appear.
  
  
• The Blum-Micali CSPRNG:
  
  
• Manuel Blum and Silvio Micali, How to Generate Cryptographically Strong Sequences of Pseudorandom Bits, SIAM Journal on Computing 13, no. 4 (1984): 850-864. 
  
  
• Elliptic curve discrete logarithms and random number generators based on them:
  
  
• The x-Logarithm Problem on elliptic curves
  
  
• NIST. SP 800-90, Recommendation for Random Number Generation Using Deterministic Random Bit Generators, March 2007.
  
  
• Daniel R.L. Brown and Kristian Gjøsteen. A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator, CRYPTO 2007, LNCS 4622, pp. 466-481, 2007.
  
  
• Aaron Blumenfeld.  Discrete Logarithms on Elliptic Curves, MSTR 10-04. Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 12, Issue 1, 2011.
  
  
• Code from "Discrete Logarithms on Elliptic Curves".
  
  
• The self-power map
  
  
• Roger Crocker, On a New Problem in Number Theory, The American Mathematical Monthly, Vol. 73, No. 4 (Apr., 1966), pp. 355-357.
  
  
• Roger Crocker, On Residues of nⁿ, The American Mathematical Monthly, Vol. 76, No. 9 (Nov., 1969), pp. 1028-1029.
  
  
• Lawrence Somer, The Residues of nⁿ Modulo p, Fibonacci Quarterly, Vol. 19, No. 2 (Apr.,  1981), pp. 110-117.
  
  
• Antal Balog, Kevin A. Broughan, Igor E. Shparlinski.  On the Number of Solutions of Exponential Congruences. Acta Arithmetica, Vol. 148 (2011), pp. 93-103.
  

• Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Variations of the ElGamal scheme, Section 11.5(i), The Handbook of Applied Cryptography, p. 457.
  

• Matthew Friedrichsen, Brian Larson, and Emily McDowell.  Structure and Statistics of the Self-Power Map, MSTR 10-05.  Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 11, Issue 2, 2010.
  
  
• Code from "Structure and Statistics of the Self-Power Map".
  
  
• The square (and higher power) discrete exponential map
  
  
• Jan Camenisch and Markus Stadler, Efficient group signature schemes for large groups, CRYPTO  ’97, LNCS 1294, pp. 410-424, 1997.
  
  
• "Multi-maps" x mod p^e → g^x mod p^e (or similar maps) for any x
  
  
• Lev Glebsky, Cycles in Repeated Exponentiation Modulo pⁿ.  Preprint.
  
  
• Joshua Holden, Margaret M. Robinson,  Counting Fixed Points, Two-Cycles, and Collisions of the Discrete Exponential Function using p-adic Methods.  To appear in the special issue of Journal of the Australian Mathematical Society dedicated to Alf van der Poorten.
  
  
• Finite fields
  
  
• Andrew M. Odlyzko, Discrete Logarithms in Finite Fields and Their Cryptographic Significance.  In Advances in Cryptology: Proceedings of EUROCRYPT 84, Volume 209 of Lecture Notes in Computer Science, Springer-Verlag, 1985.
  
  
• Brouwer, Pellikaan, Eric R. Verheul, Doing More with Fewer Bits. In Advances in Cryptology—Asiacrypt’99, Vol. 1716 of Lecture Notes in Computer Science, Springer-Verlag, 1999. pp. 321-332.
  
  
• Arjen K. Lenstra, Eric R. Verheul, The XTR public key system, Crypto 2000.
  
  
• Matrices and other groups
  
  
• Eligijus Sakalauskas, Narimantas Listopadskis, Povilas Tvarijonas, KEY AGREEMENT PROTOCOL (KAP) BASED ON MATRIX POWER FUNCTION, in Krassimir Markov, Krassimira Ivanova, Ilia Mitov (ed.), Advanced Studies in Software and Knowledge Engineering.
  
  
• Christopher J. Monico, Semirings and Semigroup Actions in Public-Key Cryptography.
  

• In-Sok Lee, Woo-Hwan Kim, Daesung Kwon, Sangil Nahm, Nam-Seok Kwak, and Yoo-Jin Baek. On the Security of MOR Public Key Cryptosystem.
  
  
• Johannes Buchmann and H. Williams, A key-exchange system based on imaginary quadratic fields, Journal of Cryptology 1, no. 2 (June 10, 1988): 107-118. 
  

• Max F. Brugger and Christina A. Frederick. The Discrete Logarithm Problem and Ternary Functional Graphs, MSTR 07-02.  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, MSTR 07-01.
  
  
• Philip Brunetti. Structural Properties of the Mapping g^x → g^x2. (Draft)
  

• Katrina Glaeser. The Digraph of the Square Mapping on Elliptic Curves, MSTR 09-08.
  
  
• Andrew Hoffman. Statistical Investigation of Structure in the Discrete Logarithm, MSTR 09-09. Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 10, Issue 2, 2009.
  
  
• Code from "Statistical Investigation of Structure in the Discrete Logarithm".


• Joseph Kramer-Miller. Structural Properties of Power Digraphs Modulo n, MSTR 09-06.

• Marcus L. Mace. Discrete Logarithm over Composite Moduli, MSTR 09-07.

• Aaron Blumenfeld.  Discrete Logarithms on Elliptic Curves, MSTR 10-04. Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 12, Issue 1, 2011.
  
  
• Code from "Discrete Logarithms on Elliptic Curves".
  
  
• Matthew Friedrichsen, Brian Larson, and Emily McDowell.  Structure and Statistics of the Self-Power Map, MSTR 10-05.  Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 11, Issue 2, 2010.
  
  
• Code from "Structure and Statistics of the Self-Power Map".
  
  

• JingJing Chen and Mark Lotts.  Structure and Randomness of the Discrete Lambert Map, MSTR 11-02.  Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 13, Issue 1, 2012.
  
  
• Code from Chen and Lotts.
  
  
• Christopher Evans.  The Elliptic Curve Discrete Logarithm and Functional Graphs, MSTR 11-01.
  
  
• Code from Evans.
  
  
• Alex Wood.  The Square Discrete Exponentiation Map, MSTR 11-05.

• Information about computers:
  
  
•  The "Theorodrome" computers (the Linux machines in the classrooms we are using)
  
  
• The RHIT parallel cluster
  
  
• The Algolib package for Maple and lots of tutorials and other information
  
  
• Information about presentations:
  
  
• Preparing and giving "20-minute" math talks
  
  
• The Indiana University Math REU Conference (may be last year's information)
  
  
• The On-Line Encyclopedia of Integer Sequences