Mapping the discrete logarithm
Authors:
- 11 August 2010
- journal article
- Published by Mathematical Sciences Publishers in Involve, a Journal of Mathematics
- Vol. 3 (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 g^a mod n. This paper focuses on a prime modulus, p, for which it is shown that the basic structure of the functional graph is largely dependent on an interaction between g and p-1. In fact, there are precisely as many different functional graph structures as there are divisors of p-1. This paper extracts two of these 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 suggests that both the permutations and binary functional graphs correspond well to the theoretical data which provides motivation to extend this to larger divisors of p-1 and study the impact this forced structure has on the many cryptographic algorithms that rely on the discrete logarithm for their security. This is especially applicable to those algorithms that require a "safe" prime (p=2q+1, where q is prime) modulus since all non-trivial functional graphs generated using a safe prime modulus can be analyzed by the framework presented here.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- An Improved Pseudo-Random Generator Based on the Discrete Logarithm ProblemJournal of Cryptology, 2004
- Random Mapping Statistics2001
- On the statistical properties of Diffie-Hellman distributionsIsrael Journal of Mathematics, 2000
- The Decision Diffie-Hellman problem1998
- The Distribution of Heights of Binary Trees and Other Simple TreesCombinatorics, Probability and Computing, 1993
- Automatic average-case analysis of algorithmsTheoretical Computer Science, 1991
- Singularity Analysis of Generating FunctionsSIAM Journal on Discrete Mathematics, 1990
- How to Generate Cryptographically Strong Sequences of Pseudorandom BitsSIAM Journal on Computing, 1984
- The average height of binary trees and other simple treesJournal of Computer and System Sciences, 1982
- New directions in cryptographyIEEE Transactions on Information Theory, 1976