Power map permutations and the discrete log problem

Abstract

For g any generator of the multiplicative subgroup of the integers modulo a prime p, we consider the permutation that maps i to $g^i$, for $1 \le i \le p -1$, the inverse of the discrete log map. Such a permutation is the composite of cycles, and if a cycle is of length n and starts with $g^s$, the last element of the cycle is s, so we can solve the DLP in at most n steps. We characterise all cycles of length 1 (fixpoints) as well as the number of generators for which an element is a fixpoint. In addition, we identify a number of conditions under which there will be orbits of length 2, 3 and 4, and provide a simple formula for switching between generators. Short orbits would all obviously provide keys that would be disastrous in public key schemes such as DSA and Diffie-Hellman and thus should be avoided. This is emerging research, and it remains to be seen if such keys can be avoided by merely using good random bit generators, or whether certain primes and generators are inherently weak.