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

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