|
|||||
 |
|
|
|
|
|
Mapping the
discrete logarithm
Daniel Cloutier and Joshua Holden
Vol. 3 (2010), No. 2, 197–213
|
Abstract |
|
The discrete logarithm is a problem that surfaces frequently in the field of cryptography as a result of using the transformation . 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, , for which it is shown that the basic structure of the functional graph produced by this map is largely dependent on an interaction between and . 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. |
Keywords
discrete logarithm problem, random map, functional graph
|
Mathematical Subject Classification 2000
Primary: 11Y16
Secondary: 11-04, 94A60, 05A15
|
Milestones
Received: 17 October 2009
Accepted: 19 June 2010
Published: 11 August 2010
Communicated by Carl Pomerance
|
Authors |
| Daniel Cloutier | |
| Rose–Hulman Institute of
Technology Terre Haute, IN 47803 United States |
|
| Joshua Holden | |
| Rose–Hulman Institute of
Technology Department of Mathematics CM #125 5500 Wabash Ave. Terre Haute, IN 47803 United States |
|
| http://www.rose-hulman.edu/~holden | |
|
