Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The self-power map and collecting all residue classes

Author: Catalina V. Anghel
Journal: Math. Comp. 85 (2016), 379-399
MSC (2010): Primary 11A07, 11K45, 11T23; Secondary 94A60
Published electronically: May 12, 2015
MathSciNet review: 3404454
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The self-power map is the function from the set of natural numbers to itself which sends the number $n$ to $n^n$. 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 $n^n \equiv a \bmod p$ has a solution $1 \le n \le x$, for every residue class $a$ modulo $p$. While $n^n \bmod 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 $p^2\log \phi (p-1)/\phi (p-1)$, using the coupon collector problem as a model. We prove the bound $x <p^{2-\alpha }$ for sufficiently large $p$ and a fixed constant $\alpha > 0$ independent of $p$, using a counting argument and exponential sum bounds.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11A07, 11K45, 11T23, 94A60

Retrieve articles in all journals with MSC (2010): 11A07, 11K45, 11T23, 94A60

Additional Information

Catalina V. Anghel
Affiliation: Department of Mathematics, University of Toronto, 40 St. George St., Toronto, ON M5S 2E4, Canada

Received by editor(s): April 21, 2013
Received by editor(s) in revised form: April 22, 2014
Published electronically: May 12, 2015
Article copyright: © Copyright 2015 American Mathematical Society