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

DOI:
https://doi.org/10.1090/mcom/2978

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.

- Catalina V. Anghel,
*The self-power map and its image modulo a prime*, ProQuest LLC, Ann Arbor, MI, 2013. Thesis (Ph.D.)–University of Toronto (Canada). MR**3211738** - Gennady Bachman,
*On an optimality property of Ramanujan sums*, Proc. Amer. Math. Soc.**125**(1997), no. 4, 1001–1003. MR**1363445**, DOI 10.1090/S0002-9939-97-03650-2 - R. Balasubramanian, private communication, 2011.
- Antal Balog, Kevin A. Broughan, and Igor E. Shparlinski,
*On the number of solutions of exponential congruences*, Acta Arith.**148**(2011), no. 1, 93–103. MR**2784012**, DOI 10.4064/aa148-1-7 - Manuel Blum and Silvio Micali,
*How to generate cryptographically strong sequences of pseudorandom bits*, SIAM J. Comput.**13**(1984), no. 4, 850–864. MR**764183**, DOI 10.1137/0213053 - Jean Bourgain and Igor E. Shparlinski,
*Distribution of consecutive modular roots of an integer*, Acta Arith.**134**(2008), no. 1, 83–91. MR**2429637**, DOI 10.4064/aa134-1-6 - Roger Crocker,
*On residues of $n^{n}$*, Amer. Math. Monthly**76**(1969), 1028–1029. MR**248072**, DOI 10.2307/2317129 - P. Erdős and A. Rényi,
*On a classical problem of probability theory*, Magyar Tud. Akad. Mat. Kutató Int. Közl.**6**(1961), 215–220 (English, with Russian summary). MR**150807** - P. Erdős and P. Turán,
*On a problem in the theory of uniform distribution, I, II*, Indag. Math.**10**(1948), 370–378; 406–413. - Philippe Flajolet, Danièle Gardy, and Loÿs Thimonier,
*Birthday paradox, coupon collectors, caching algorithms and self-organizing search*, Discrete Appl. Math.**39**(1992), no. 3, 207–229. MR**1189469**, DOI 10.1016/0166-218X(92)90177-C - Philippe Flajolet and Robert Sedgewick,
*Analytic combinatorics*, Cambridge University Press, Cambridge, 2009. MR**2483235**, DOI 10.1017/CBO9780511801655 - W. K. Hayman,
*A generalisation of Stirling’s formula*, J. Reine Angew. Math.**196**(1956), 67–95. MR**80749**, DOI 10.1515/crll.1956.196.67 - Joshua Holden,
*Fixed points and two-cycles of the discrete logarithm*, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 405–415. MR**2041100**, DOI 10.1007/3-540-45455-1_{3}2 - J. F. Koksma,
*Some theorems on Diophantine inequalities*, Scriptum no. 5, Math. Centrum Amsterdam, 1950. MR**0038379** - L. Kuipers and H. Niederreiter,
*Uniform distribution of sequences*, Dover Publications, Inc., 2006. - Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone,
*Handbook of applied cryptography*, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1997. With a foreword by Ronald L. Rivest. MR**1412797** - M. Ram Murty,
*Small solutions of polynomial congruences*, Indian J. Pure Appl. Math.**41**(2010), no. 1, 15–23. MR**2650097**, DOI 10.1007/s13226-010-0015-z - I. Niven, H. S. Zuckerman, and H. L. Montogomery,
*An Introduction to the Theory of Numbers*, 5th edition, John Wiley & Sons, Inc., 1991. - Igor E. Shparlinski,
*Exponential sums with consecutive modular roots of an integer*, Q. J. Math.**62**(2011), no. 1, 207–213. MR**2774362**, DOI 10.1093/qmath/hap023 - Lawrence Somer,
*The residues of $n^{n}$ modulo $p$*, Fibonacci Quart.**19**(1981), no. 2, 110–117. MR**614045** - P. Szűsz,
*On a problem in the theory of uniform distribution (Hungarian)*, Compt. Rend. Premier Congrès Hongrois (1952), 461–472.

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

Email:
catalina.anghel@alum.utoronto.ca

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