{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,13]],"date-time":"2025-04-13T04:53:38Z","timestamp":1744520018711,"version":"3.30.1"},"reference-count":26,"publisher":"American Mathematical Society (AMS)","issue":"236","license":[{"start":{"date-parts":[[2001,7,13]],"date-time":"2001-07-13T00:00:00Z","timestamp":994982400000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

Consider the pseudorandom number generatoru<\/mml:mi>n<\/mml:mi><\/mml:msub>\u2261<\/mml:mo>u<\/mml:mi>n<\/mml:mi>\u2212<\/mml:mo>1<\/mml:mn><\/mml:mrow>e<\/mml:mi><\/mml:msubsup>(<\/mml:mo>mod<\/mml:mi>m<\/mml:mi>)<\/mml:mo>,<\/mml:mo>0<\/mml:mn>\u2264<\/mml:mo>u<\/mml:mi>n<\/mml:mi><\/mml:msub>\u2264<\/mml:mo>m<\/mml:mi>\u2212<\/mml:mo>1<\/mml:mn>,<\/mml:mo>n<\/mml:mi>=<\/mml:mo>1<\/mml:mn>,<\/mml:mo>2<\/mml:mn>,<\/mml:mo>\u2026<\/mml:mo>,<\/mml:mo><\/mml:mrow>\\begin{equation*} u_n\\equiv u_{n-1}^e\\pmod {m},\\quad 0\\le u_n\\le m-1,\\quad n=1,2,\\ldots , \\end{equation*}<\/mml:annotation><\/mml:semantics><\/mml:math><\/disp-formula>where we are given the modulusm<\/mml:mi>m<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>, the initial valueu<\/mml:mi>0<\/mml:mn><\/mml:msub>=<\/mml:mo>\u03d1<\/mml:mi><\/mml:mrow>u_0=\\vartheta<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>and the exponente<\/mml:mi>e<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>. One case of particular interest is when the modulusm<\/mml:mi>m<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>is of the formp<\/mml:mi>l<\/mml:mi><\/mml:mrow>pl<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>, wherep<\/mml:mi>,<\/mml:mo>l<\/mml:mi><\/mml:mrow>p,l<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>are different primes of the same magnitude. It is known from work of the first and third authors that for modulim<\/mml:mi>=<\/mml:mo>p<\/mml:mi>l<\/mml:mi><\/mml:mrow>m=pl<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>, if the period of the sequence(<\/mml:mo>u<\/mml:mi>n<\/mml:mi><\/mml:msub>)<\/mml:mo><\/mml:mrow>(u_n)<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>exceedsm<\/mml:mi>3<\/mml:mn>\/<\/mml:mo><\/mml:mrow>4<\/mml:mn>+<\/mml:mo>\u03b5<\/mml:mi><\/mml:mrow><\/mml:msup>m^{3\/4+\\varepsilon }<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>, then the sequence is uniformly distributed. We show rigorously that for almost all choices ofp<\/mml:mi>,<\/mml:mo>l<\/mml:mi><\/mml:mrow>p,l<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>it is the case that for almost all choices of\u03d1<\/mml:mi>,<\/mml:mo>e<\/mml:mi><\/mml:mrow>\\vartheta ,e<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>, the period of the power generator exceeds(<\/mml:mo>p<\/mml:mi>l<\/mml:mi>)<\/mml:mo>1<\/mml:mn>\u2212<\/mml:mo>\u03b5<\/mml:mi><\/mml:mrow><\/mml:msup><\/mml:mrow>(pl)^{1-\\varepsilon }<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>. And so, in this case, the power generator is uniformly distributed. We also give some other cryptographic applications, namely, to ruling-out the cycling attack on the RSA cryptosystem and to so-called time-release crypto. The principal tool is an estimate related to the Carmichael function\u03bb<\/mml:mi>(<\/mml:mo>m<\/mml:mi>)<\/mml:mo><\/mml:mrow>\\lambda (m)<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>, the size of the largest cyclic subgroup of the multiplicative group of residues modulom<\/mml:mi>m<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>. In particular, we show that for any\u0394<\/mml:mi>\u2265<\/mml:mo>(<\/mml:mo>log<\/mml:mi>\u2061<\/mml:mo>log<\/mml:mi>\u2061<\/mml:mo>N<\/mml:mi>)<\/mml:mo>3<\/mml:mn><\/mml:msup><\/mml:mrow>\\Delta \\ge (\\log \\log N)^3<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>, we have\u03bb<\/mml:mi>(<\/mml:mo>m<\/mml:mi>)<\/mml:mo>\u2265<\/mml:mo>N<\/mml:mi>exp<\/mml:mi>\u2061<\/mml:mo>(<\/mml:mo>\u2212<\/mml:mo>\u0394<\/mml:mi>)<\/mml:mo><\/mml:mrow>\\lambda (m)\\ge N\\exp (-\\Delta )<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>for all integersm<\/mml:mi>m<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>with1<\/mml:mn>\u2264<\/mml:mo>m<\/mml:mi>\u2264<\/mml:mo>N<\/mml:mi><\/mml:mrow>1\\le m\\le N<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>, apart from at mostN<\/mml:mi>exp<\/mml:mi>\u2061<\/mml:mo>(<\/mml:mo>\u2212<\/mml:mo>0.69<\/mml:mn>(<\/mml:mo>\u0394<\/mml:mi>log<\/mml:mi>\u2061<\/mml:mo>\u0394<\/mml:mi>)<\/mml:mo><\/mml:mrow>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>3<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow>N\\exp \\left (-0.69\\left (\\Delta \\log \\Delta \\right )^{1\/3}\\right )<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>exceptions.<\/p>","DOI":"10.1090\/s0025-5718-00-01282-5","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T22:13:53Z","timestamp":1027721633000},"page":"1591-1605","source":"Crossref","is-referenced-by-count":34,"title":["Period of the power generator and small values of Carmichael\u2019s function"],"prefix":"10.1090","volume":"70","author":[{"given":"John","family":"Friedlander","sequence":"first","affiliation":[]},{"given":"Carl","family":"Pomerance","sequence":"additional","affiliation":[]},{"given":"Igor","family":"Shparlinski","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2000,7,13]]},"reference":[{"issue":"3","key":"1","doi-asserted-by":"publisher","first-page":"703","DOI":"10.2307\/2118576","article-title":"There are infinitely many Carmichael numbers","volume":"139","author":"Alford, W. R.","year":"1994","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"issue":"4","key":"2","doi-asserted-by":"publisher","first-page":"331","DOI":"10.4064\/aa-83-4-331-361","article-title":"Shifted primes without large prime factors","volume":"83","author":"Baker, R. C.","year":"1998","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"3","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-1-4612-3464-7_5","article-title":"The prime \ud835\udc58-tuplets conjecture on average","author":"Balog, Antal","year":"1990"},{"issue":"2","key":"4","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0215025","article-title":"A simple unpredictable pseudorandom number generator","volume":"15","author":"Blum, L.","year":"1986","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"issue":"3","key":"5","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1023\/A:1008289605486","article-title":"Analysis of iterated modular exponentiation: the orbits of \ud835\udc65^{\ud835\udefc}\\bmod\ud835\udc41","volume":"13","author":"Brennan, J. J.","year":"1998","journal-title":"Des. Codes Cryptogr.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-1022","issn-type":"print"},{"issue":"1","key":"6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0022-314X(83)90002-1","article-title":"On a problem of Oppenheim concerning \u201cfactorisatio numerorum\u201d","volume":"17","author":"Canfield, E. R.","year":"1983","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"issue":"4","key":"7","doi-asserted-by":"publisher","first-page":"1155","DOI":"10.1109\/18.391261","article-title":"Properties of the \ud835\udc65\u00b2 mod \ud835\udc41 pseudorandom number generator","volume":"41","author":"Cusick, Thomas W.","year":"1995","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"8","series-title":"North-Holland Mathematical Library","isbn-type":"print","volume-title":"Stream ciphers and number theory","volume":"55","author":"Cusick, Thomas W.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/0444828737"},{"issue":"4","key":"9","doi-asserted-by":"publisher","first-page":"363","DOI":"10.4064\/aa-58-4-363-385","article-title":"Carmichael\u2019s lambda function","volume":"58","author":"Erd\u0151s, Paul","year":"1991","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"10","doi-asserted-by":"crossref","unstructured":"R. Fischlin and C. P. Schnorr, \u2018Stronger security proofs for RSA and Rabin bits\u2019, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1233 (1997), 267\u2013279.","DOI":"10.1007\/3-540-69053-0_19"},{"key":"11","doi-asserted-by":"crossref","unstructured":"J. B. Friedlander, D. Lieman and I. E. Shparlinski, \u2018On the distribution of the RSA generator\u2019, Proc. Intern. Conf. on Sequences and their Applications (SETA\u201998), Singapore, Springer-Verlag, London, 1999, 205\u2013212.","DOI":"10.1007\/978-1-4471-0551-0_14"},{"key":"12","unstructured":"J. B. Friedlander and I. E. Shparlinski, \u2018On the distribution of the power generator\u2019, Math. Comp., (to appear)."},{"key":"13","unstructured":"F. Griffin and I. E. Shparlinski, \u2018On the linear complexity profile of the power generator\u2019, Preprint, 1998, 1\u201311."},{"key":"14","series-title":"London Mathematical Society Monographs, No. 4","volume-title":"Sieve methods","author":"Halberstam, H.","year":"1974"},{"key":"15","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad and M. N\u00e4slund, \u2018The security of individual RSA bits\u2019, Proc. 39th IEEE Symp. on Foundations of Comp. Sci., 1998, 510\u2013519.","DOI":"10.1109\/SFCS.1998.743502"},{"issue":"2","key":"16","doi-asserted-by":"crossref","first-page":"411","DOI":"10.5802\/jtnb.101","article-title":"Integers without large prime factors","volume":"5","author":"Hildebrand, Adolf","year":"1993","journal-title":"J. Th\\'{e}or. Nombres Bordeaux","ISSN":"https:\/\/id.crossref.org\/issn\/1246-7405","issn-type":"print"},{"key":"17","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1090\/psapm\/042\/1095554","article-title":"Pseudorandom number generators in cryptography and number theory","author":"Lagarias, J. C.","year":"1990"},{"issue":"3","key":"18","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/BF00202269","article-title":"Fast generation of prime numbers and secure public-key cryptographic parameters","volume":"8","author":"Maurer, Ueli M.","year":"1995","journal-title":"J. Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"key":"19","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"},{"key":"20","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1515\/crll.1977.293-294.217","article-title":"On the distribution of amicable numbers","volume":"293(294)","author":"Pomerance, Carl","year":"1977","journal-title":"J. Reine Angew. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0075-4102","issn-type":"print"},{"key":"21","doi-asserted-by":"publisher","first-page":"771","DOI":"10.2307\/2371335","article-title":"Infinite number fields with Noether ideal theories","volume":"61","author":"MacLane, Saunders","year":"1939","journal-title":"Amer. J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9327","issn-type":"print"},{"key":"22","doi-asserted-by":"crossref","unstructured":"R. L. Rivest, \u2018Remarks on a proposed cryptanalytic attack on the M.I.T. public-key cryptosystem\u2019, Cryptologia, 2 (1978), 62\u201365.","DOI":"10.1080\/0161-117891852785"},{"key":"23","unstructured":"R. L. Rivest, A. Shamir and D. A. Wagner, \u2018Time-lock puzzles and timed-release crypto\u2019, Preprint, 1996, 1\u20139."},{"key":"24","unstructured":"R. L. Rivest and R. D. Silverman, \u2018Are \u201cstrong\u201d primes needed for RSA?\u2019, Preprint, 1999, 1\u201323."},{"key":"25","unstructured":"I. E. Shparlinski, \u2018On the linear complexity of the power generator\u2019, Designs, Codes and Cryptography, (to appear)."},{"key":"26","series-title":"CRC Press Series on Discrete Mathematics and its Applications","isbn-type":"print","volume-title":"Cryptography","author":"Stinson, Douglas R.","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/0849385210"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2001-70-236\/S0025-5718-00-01282-5\/S0025-5718-00-01282-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-236\/S0025-5718-00-01282-5\/S0025-5718-00-01282-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,8]],"date-time":"2024-12-08T10:35:17Z","timestamp":1733654117000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-236\/S0025-5718-00-01282-5\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,7,13]]},"references-count":26,"journal-issue":{"issue":"236","published-print":{"date-parts":[[2001,10]]}},"alternative-id":["S0025-5718-00-01282-5"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-00-01282-5","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["0025-5718","1088-6842"],"issn-type":[{"type":"print","value":"0025-5718"},{"type":"electronic","value":"1088-6842"}],"subject":[],"published":{"date-parts":[[2000,7,13]]}}}