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