Mapping the discrete logarithm

DOI10.2140/INVOLVE.2010.3.197zbMATH Open1269.11123arXivmath/0605024OpenAlexW2127703673MaRDI QIDQ992555FDOQ992555

Authors: Daniel Cloutier, Joshua Holden 

Publication date: 9 September 2010

Published in: Involve (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/0605024

Recommendations

• scientific article; zbMATH DE number 6693372
• Discrete logarithms on elliptic curves
• scientific article; zbMATH DE number 4214161
• Structure and randomness of the discrete Lambert map
• The discrete logarithm problem

zbMATH Keywords

discrete logarithm problemrandom mapfunctional graph

Mathematics Subject Classification ID

Cryptography (94A60) Exact enumeration problems, generating functions (05A15) Number-theoretic algorithms; complexity (11Y16)

Cited In (6)

• Structure and statistics of the self-power map
• On sunlet graphs connected to a specific map on $\{1, 2, \ldots, p - 1\}$
• Statistics for fixed points of the self-power map
• Power map permutations and the discrete log problem
• Quantum attacks on pseudorandom generators
• Structure and randomness of the discrete Lambert map

This page was built for publication: Mapping the discrete logarithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q992555)