MAPPING THE DISCRETE LOGARITHM
an Undergraduate Research Project,
funded by National Science Foundation REU grants
DMS0352940, DMS1003924
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,
DiffieHellman key exchange, RSA and the BlumMicali 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?
Mapping the Discrete Logarithm talk notes:
Some references (more available on request):
 General:
 Comparing discrete exponentiation maps with random maps:

Daniel R. Cloutier. Mapping
the discrete logarithm. Senior thesis, RoseHulman
Institute of Technology, 2005.
 Code
from "Mapping the Discrete Logarithm"

Daniel R. Cloutier and Joshua Holden. Mapping
the discrete logarithm. Involve, 3:197213,
2010.
 Nathan W. Lindle. A
Statistical Look at Maps of the Discrete Logarithm.
Senior thesis, RoseHulman 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 0702. Also
published in the RoseHulman 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 0909. Also
published in the RoseHulman 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 0907.
 Counting random maps and related objects:
 Philippe Flajolet and Andrew Odlyzko. Random Mapping Statistics.
In Advances in Cryptology, Proc. Eurocrypt'89, ,
JJ. Quisquater Ed., Lect. Notes in Comp. Sc.
vol 434, 1990, pp. 329354.
 Philippe Flajolet and Andrew Odlyzko. Singularity
analysis of generating functions. In SIAM
J. Discrete Math., vol 3 (1990) pp. 216240.
 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. 171213.
 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.
145156.
 Herbert Wilf, Generatingfunctionology,
2nd ed., Academic Press, 1994.
 Other related analyses of discrete exponentiation maps:
 Joshua Holden. Fixed
Points
and
TwoCycles
of
the
Discrete Logarithm. In: Algorithmic number theory:
5th international symposium; proceedings, no. 2369 in
Springer Lecture Notes in Computer Science, SpringerVerlag,
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:419449, 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 BlumMicali CSPRNG:
 Elliptic curve discrete logarithms and random number
generators based on them:
 The
xLogarithm
Problem
on
elliptic
curves
 NIST. SP
80090A,
Recommendation
for
Random
Number Generation Using Deterministic Random Bit Generators,
January 2012.
 Daniel R.L. Brown and Kristian Gjøsteen. A
Security Analysis of the NIST SP 80090 Elliptic Curve
Random Number Generator, CRYPTO 2007, LNCS 4622, pp.
466481, 2007.
 Aaron Blumenfeld. Discrete
Logarithms on Elliptic Curves, MSTR 1004. Also
published in the RoseHulman Undergraduate
Mathematics Journal, Vol. 12, Issue 1, 2011.
 Code from "Discrete
Logarithms on Elliptic Curves".
 The selfpower map
 Roger Crocker, On a
New Problem in Number Theory, The American Mathematical Monthly, Vol. 73,
No. 4 (Apr., 1966), pp. 355357.
 Roger Crocker, On
Residues of n^{n}, The American Mathematical
Monthly, Vol. 76, No. 9 (Nov., 1969), pp. 10281029.
 Lawrence Somer, The
Residues of n^{n} Modulo p, Fibonacci
Quarterly, Vol. 19, No. 2 (Apr., 1981), pp.
110117.
 Antal Balog, Kevin A. Broughan, Igor E. Shparlinski. On the
Number of Solutions of Exponential Congruences. Acta
Arithmetica, Vol. 148 (2011), pp. 93103.

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
SelfPower Map, MSTR 1005. Also
published in the RoseHulman Undergraduate
Mathematics Journal, Vol. 11, Issue 2, 2010.
 Code from
"Structure and Statistics of the SelfPower Map".
 The square (and higher power) discrete exponential map
 "Multimaps" x mod p^{e} →
g^{x} mod p^{e} (or similar
maps) for any x
 Finite fields

 Brouwer, Pellikaan, Eric R. Verheul, Doing
More with Fewer Bits. In Advances in
Cryptology—Asiacrypt’99, Vol. 1716 of Lecture Notes in
Computer Science, SpringerVerlag, 1999. pp. 321332.
 Arjen K. Lenstra, Eric R. Verheul, The
XTR public key system, Crypto 2000.
 Matrices and other groups
Reports from the 2007 REU:
Reports from the 2009 REU:
Reports from the 2010 REU:
 Aaron Blumenfeld. Discrete
Logarithms on Elliptic Curves, MSTR 1004. Also
published in the RoseHulman 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
SelfPower Map, MSTR 1005. Also
published in the RoseHulman Undergraduate Mathematics
Journal, Vol. 11, Issue 2, 2010.
 Code from "Structure
and Statistics of the SelfPower Map".
Reports from the 2011 REU:
Other resources: