The self-power map and its image modulo a prime
Catalina V. Anghel · TSpace (University of Toronto) · 2013
The self-power map is the function from the set of natural numbers to itself which sends the number n to nn. Motivated by applications to cryptography, we consider the image of this map modulo a prime p. We study the question of how large x must be so that nn a mod p has a solution with 1 ≤ n ≤ x, for every residue class a modulo p. While nn mod p is not uniformly distributed, it does appear to behave in certain ways as a random function. We give a heuristic argument to show that the expected x is approximately p2 log &phis;(p − 1)/&phis;(p − 1), using the coupon collector problem as a model. Rigorously, we prove the bound x 0 independent of p, using a counting argument and exponential sum bounds. Additionally, we prove nontrivial bounds on the number of solutions of nn ≡ a mod p for a fixed residue class a when 1 ≤ n ≤ x, extending the known bounds when 1 ≤ n ≤ p − 1.