{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T19:35:39Z","timestamp":1776800139899,"version":"3.51.2"},"reference-count":21,"publisher":"American Mathematical Society (AMS)","issue":"297","license":[{"start":{"date-parts":[[2016,5,12]],"date-time":"2016-05-12T00:00:00Z","timestamp":1463011200000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n The self-power map is the function from the set of natural numbers to itself which sends the number\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n to\n \n \n \n \n n<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n n^n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . Motivated by applications to cryptography, we consider the image of this map modulo a prime\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We study the question of how large\n \n \n \n x<\/mml:mi>\n x<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n must be so that\n \n \n \n \n \n n<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n \n \u2261\n \n <\/mml:mo>\n a<\/mml:mi>\n mod<\/mml:mo>\n p<\/mml:mi>\n <\/mml:mrow>\n n^n \\equiv a \\bmod p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n has a solution\n \n \n \n \n 1<\/mml:mn>\n \n \u2264\n \n <\/mml:mo>\n n<\/mml:mi>\n \n \u2264\n \n <\/mml:mo>\n x<\/mml:mi>\n <\/mml:mrow>\n 1 \\le n \\le x<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , for every residue class\n \n \n \n a<\/mml:mi>\n a<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n modulo\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . While\n \n \n \n \n \n n<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n mod<\/mml:mo>\n p<\/mml:mi>\n <\/mml:mrow>\n n^n \\bmod p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n 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\n \n \n \n x<\/mml:mi>\n x<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is approximately\n \n \n \n \n \n p<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n \n \u03d5\n \n <\/mml:mi>\n (<\/mml:mo>\n p<\/mml:mi>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n \n \u03d5\n \n <\/mml:mi>\n (<\/mml:mo>\n p<\/mml:mi>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n p^2\\log \\phi (p-1)\/\\phi (p-1)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , using the coupon collector problem as a model. We prove the bound\n \n \n \n \n x<\/mml:mi>\n ><\/mml:mo>\n \n p<\/mml:mi>\n \n 2<\/mml:mn>\n \n \u2212\n \n <\/mml:mo>\n \n \u03b1\n \n <\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n x >p^{2-\\alpha }<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for sufficiently large\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and a fixed constant\n \n \n \n \n \n \u03b1\n \n <\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n \\alpha > 0<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n independent of\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , using a counting argument and exponential sum bounds.\n <\/p>","DOI":"10.1090\/mcom\/2978","type":"journal-article","created":{"date-parts":[[2015,10,6]],"date-time":"2015-10-06T13:04:45Z","timestamp":1444136685000},"page":"379-399","source":"Crossref","is-referenced-by-count":4,"title":["The self-power map and collecting all residue classes"],"prefix":"10.1090","volume":"85","author":[{"given":"Catalina","family":"Anghel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2015,5,12]]},"reference":[{"key":"1","isbn-type":"print","volume-title":"The self-power map and its image modulo a prime","author":"Anghel, Catalina V.","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9780499220073"},{"issue":"4","key":"2","doi-asserted-by":"publisher","first-page":"1001","DOI":"10.1090\/S0002-9939-97-03650-2","article-title":"On an optimality property of Ramanujan sums","volume":"125","author":"Bachman, Gennady","year":"1997","journal-title":"Proc. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9939","issn-type":"print"},{"key":"3","unstructured":"R. Balasubramanian, private communication, 2011."},{"issue":"1","key":"4","doi-asserted-by":"publisher","first-page":"93","DOI":"10.4064\/aa148-1-7","article-title":"On the number of solutions of exponential congruences","volume":"148","author":"Balog, Antal","year":"2011","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"issue":"4","key":"5","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","article-title":"How to generate cryptographically strong sequences of pseudorandom bits","volume":"13","author":"Blum, Manuel","year":"1984","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"issue":"1","key":"6","doi-asserted-by":"publisher","first-page":"83","DOI":"10.4064\/aa134-1-6","article-title":"Distribution of consecutive modular roots of an integer","volume":"134","author":"Bourgain, Jean","year":"2008","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"7","doi-asserted-by":"publisher","first-page":"1028","DOI":"10.2307\/2317129","article-title":"On residues of \ud835\udc5b\u207f","volume":"76","author":"Crocker, Roger","year":"1969","journal-title":"Amer. Math. Monthly","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9890","issn-type":"print"},{"key":"8","first-page":"215","article-title":"On a classical problem of probability theory","volume":"6","author":"Erd\u0151s, P.","year":"1961","journal-title":"Magyar Tud. Akad. Mat. Kutat\\'{o} Int. K\\\"{o}zl.","ISSN":"https:\/\/id.crossref.org\/issn\/0541-9514","issn-type":"print"},{"key":"9","unstructured":"P. Erd\u0151s and P. Tur\u00e1n, On a problem in the theory of uniform distribution, I, II, Indag. Math. 10 (1948), 370\u2013378; 406\u2013413."},{"issue":"3","key":"10","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0166-218X(92)90177-C","article-title":"Birthday paradox, coupon collectors, caching algorithms and self-organizing search","volume":"39","author":"Flajolet, Philippe","year":"1992","journal-title":"Discrete Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0166-218X","issn-type":"print"},{"key":"11","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic combinatorics","author":"Flajolet, Philippe","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521898065"},{"key":"12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1515\/crll.1956.196.67","article-title":"A generalisation of Stirling\u2019s formula","volume":"196","author":"Hayman, W. K.","year":"1956","journal-title":"J. Reine Angew. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0075-4102","issn-type":"print"},{"key":"13","isbn-type":"print","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/3-540-45455-1_32","article-title":"Fixed points and two-cycles of the discrete logarithm","author":"Holden, Joshua","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/3540438637"},{"key":"14","series-title":"Scriptum, no. 5","volume-title":"Some theorems on Diophantine inequalities","author":"Koksma, J. F.","year":"1950"},{"key":"15","unstructured":"L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Dover Publications, Inc., 2006."},{"key":"16","series-title":"CRC Press Series on Discrete Mathematics and its Applications","isbn-type":"print","volume-title":"Handbook of applied cryptography","author":"Menezes, Alfred J.","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/0849385237"},{"issue":"1","key":"17","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/s13226-010-0015-z","article-title":"Small solutions of polynomial congruences","volume":"41","author":"Murty, M. Ram","year":"2010","journal-title":"Indian J. Pure Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0019-5588","issn-type":"print"},{"key":"18","unstructured":"I. Niven, H. S. Zuckerman, and H. L. Montogomery, An Introduction to the Theory of Numbers, 5th edition, John Wiley & Sons, Inc., 1991."},{"issue":"1","key":"19","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1093\/qmath\/hap023","article-title":"Exponential sums with consecutive modular roots of an integer","volume":"62","author":"Shparlinski, Igor E.","year":"2011","journal-title":"Q. J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0033-5606","issn-type":"print"},{"issue":"2","key":"20","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1080\/00150517.1981.12430097","article-title":"The residues of \ud835\udc5b\u207f modulo \ud835\udc5d","volume":"19","author":"Somer, Lawrence","year":"1981","journal-title":"Fibonacci Quart.","ISSN":"https:\/\/id.crossref.org\/issn\/0015-0517","issn-type":"print"},{"key":"21","unstructured":"P. Sz\u0171sz, On a problem in the theory of uniform distribution (Hungarian), Compt. Rend. Premier Congr\u00e8s Hongrois (1952), 461\u2013472."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-02978-0\/S0025-5718-2015-02978-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-02978-0\/S0025-5718-2015-02978-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:38:26Z","timestamp":1776796706000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-02978-0\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,12]]},"references-count":21,"journal-issue":{"issue":"297","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["S0025-5718-2015-02978-0"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/2978","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2015,5,12]]}}}