Mapping the discrete logarithm
Daniel R. Cloutier, Joshua Holden · Involve a Journal of Mathematics · 2010
The discrete logarithm is a problem that surfaces frequently in the field of cryptography as a result of using the transformation x → g x mod n.Analysis of the security of many cryptographic algorithms depends on the assumption that it is statistically impossible to distinguish the use of this map from the use of a randomly chosen map with similar characteristics.This paper focuses on a prime modulus, p, for which it is shown that the basic structure of the functional graph produced by this map is largely dependent on an interaction between g and p -1.We deal with two of the possible structures, permutations and binary functional graphs.Estimates exist for the shape of a random permutation, but similar estimates must be created for the binary functional graphs.Experimental data suggest that both the permutations and binary functional graphs correspond well to the theoretical predictions.