{"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":1744520018549,"version":"3.30.1"},"reference-count":30,"publisher":"American Mathematical Society (AMS)","issue":"236","license":[{"start":{"date-parts":[[2001,10,17]],"date-time":"2001-10-17T00:00:00Z","timestamp":1003276800000},"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":"<p>We present a new method to study the power generator of pseudorandom numbers modulo a Blum integer<inline-formula content-type=\"math\/mathml\"><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"m\"><mml:semantics><mml:mi>m<\/mml:mi><mml:annotation encoding=\"application\/x-tex\">m<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>. This includes as special cases the RSA generator and the Blum\u2013Blum\u2013Shub generator. We prove the uniform distribution of these, provided that the period<inline-formula content-type=\"math\/mathml\"><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"t greater-than-or-equal-to m Superscript 3 slash 4 plus delta\"><mml:semantics><mml:mrow><mml:mi>t<\/mml:mi><mml:mo>\u2265<\/mml:mo><mml:msup><mml:mi>m<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mn>3<\/mml:mn><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:mn>4<\/mml:mn><mml:mo>+<\/mml:mo><mml:mi>\u03b4<\/mml:mi><\/mml:mrow><\/mml:msup><\/mml:mrow><mml:annotation encoding=\"application\/x-tex\">t\\ge m^{3\/4 + \\delta }<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>with fixed<inline-formula content-type=\"math\/mathml\"><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"delta greater-than 0\"><mml:semantics><mml:mrow><mml:mi>\u03b4<\/mml:mi><mml:mo>&gt;<\/mml:mo><mml:mn>0<\/mml:mn><\/mml:mrow><mml:annotation encoding=\"application\/x-tex\">\\delta &gt; 0<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>and, under the same condition, the uniform distribution of a positive proportion of the leftmost and rightmost bits. This sharpens and generalizes previous results which dealt with the RSA generator, provided the period<inline-formula content-type=\"math\/mathml\"><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"t greater-than-or-equal-to m Superscript 23 slash 24 plus delta\"><mml:semantics><mml:mrow><mml:mi>t<\/mml:mi><mml:mo>\u2265<\/mml:mo><mml:msup><mml:mi>m<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mn>23<\/mml:mn><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:mn>24<\/mml:mn><mml:mo>+<\/mml:mo><mml:mi>\u03b4<\/mml:mi><\/mml:mrow><\/mml:msup><\/mml:mrow><mml:annotation encoding=\"application\/x-tex\">t\\ge m^{23\/24 + \\delta }<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>. We apply our results to deduce that the period of the binary sequence of the rightmost bit has exponential length.<\/p>","DOI":"10.1090\/s0025-5718-00-01283-7","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T22:13:53Z","timestamp":1027721633000},"page":"1575-1589","source":"Crossref","is-referenced-by-count":28,"title":["On the distribution of the power generator"],"prefix":"10.1090","volume":"70","author":[{"given":"John","family":"Friedlander","sequence":"first","affiliation":[]},{"given":"Igor","family":"Shparlinski","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2000,10,17]]},"reference":[{"issue":"2","key":"1","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":"2","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"},{"key":"3","unstructured":"R. Canetti, J. B. Friedlander, S. Konyagin, M. Larsen, D. Lieman and I. E. Shparlinski, \u2018On the statistical properties of Diffie\u2013Hellman distributions\u2019, Israel J. Math. (to appear)."},{"issue":"3","key":"4","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1112\/S002461079900736X","article-title":"On certain exponential sums and the distribution of Diffie-Hellman triples","volume":"59","author":"Canetti, Ran","year":"1999","journal-title":"J. London Math. Soc. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0024-6107","issn-type":"print"},{"issue":"4","key":"5","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/1385-7258(80)90038-4","article-title":"The Vinogradov-Mordell-Tiet\u00e4v\u00e4inen inequalities","volume":"42","author":"Chalk, J. H. H.","year":"1980","journal-title":"Nederl. Akad. Wetensch. Indag. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0019-3577","issn-type":"print"},{"issue":"4","key":"6","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":"7","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"},{"key":"8","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":"9","unstructured":"J. B. Friedlander, J. Hansen and I. E. Shparlinski, \u2018Character sums with exponential functions\u2019, Mathematika (to appear)."},{"key":"10","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-212.","DOI":"10.1007\/978-1-4471-0551-0_14"},{"key":"11","unstructured":"J. B. Friedlander, C. Pomerance and I. E. Shparlinski, \u2018Period of the power generator and small values of Carmichael\u2019s function\u2019, Math. Comp. (to appear)."},{"key":"12","unstructured":"F. Griffin and I. E. Shparlinski, \u2018On the linear complexity profile of the power generator\u2019, Preprint, 1998, 1\u201311."},{"key":"13","doi-asserted-by":"crossref","unstructured":"F. Griffin, H. Niederreiter and I. E. Shparlinski, \u2018On the distribution of nonlinear recursive congruential pseudorandom numbers of higher orders, Proc. the 13th Symp. on Appl. Algebra, Algebraic Algorithms, and Error-Correcting Codes, Hawaii, 1999, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1999, v.1719, 87\u201393.","DOI":"10.1007\/3-540-46796-3_9"},{"key":"14","doi-asserted-by":"crossref","unstructured":"J. Gutierrez, H. Niederreiter and I. E. Shparlinski, \u2018On the multidimensional distribution of inversive congruential pseudorandom numbers in parts of the period\u2019, Monatsh. Math. 129 (2000) 31\u201336.","DOI":"10.1007\/s006050050004"},{"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"},{"key":"16","first-page":"654","article-title":"The distribution of digits in periodic fractions","volume":"89(131)","author":"Korobov, N. M.","year":"1972","journal-title":"Mat. Sb. (N.S.)"},{"key":"17","series-title":"Mathematics and its Applications (Soviet Series)","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-8032-8","volume-title":"Exponential sums and their applications","volume":"80","author":"Korobov, N. M.","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/0792316479"},{"key":"18","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"},{"key":"19","series-title":"Encyclopedia of Mathematics and its Applications","isbn-type":"print","volume-title":"Finite fields","volume":"20","author":"Lidl, Rudolf","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/0521392314","edition":"2"},{"key":"20","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":"6","key":"21","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1090\/S0002-9904-1978-14532-7","article-title":"Quasi-Monte Carlo methods and pseudo-random numbers","volume":"84","author":"Niederreiter, Harald","year":"1978","journal-title":"Bull. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9904","issn-type":"print"},{"key":"22","series-title":"CBMS-NSF Regional Conference Series in Applied Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970081","volume-title":"Random number generation and quasi-Monte Carlo methods","volume":"63","author":"Niederreiter, Harald","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/0898712955"},{"key":"23","unstructured":"H. Niederreiter and I. E. Shparlinski, \u2018On the distribution of inversive congruential pseudorandom numbers in parts of the period\u2019, Math. Comp. (to appear)."},{"key":"24","doi-asserted-by":"crossref","unstructured":"H. Niederreiter and I. E. Shparlinski, \u2018On the distribution and lattice structure of nonlinear congruential pseudorandom numbers\u2019, Finite Fields and Their Appl., 5 (1999), 246\u2013253.","DOI":"10.1006\/ffta.1999.0257"},{"key":"25","unstructured":"H. Niederreiter and I. E. Shparlinski, \u2018On the distribution of inversive congruential pseudorandom numbers modulo a prime power\u2019, Acta Arithm. (to appear)."},{"key":"26","doi-asserted-by":"crossref","unstructured":"H. Niederreiter and I. E. Shparlinski, \u2018On the distribution of pseudorandom numbers and vectors generated by inversive methods\u2019, Appl. Algebra in Engin., Commun. and Computing, 10 (2000) 189\u2013202.","DOI":"10.1007\/s002000050124"},{"key":"27","unstructured":"R. A. Rueppel, \u2018Stream ciphers\u2019, Contemporary cryptology: The science of information integrity, IEEE Press, NY, 1992, 65\u2013134."},{"key":"28","unstructured":"I. E. Shparlinski, \u2018On the linear complexity of the power generator\u2019, Designs, Codes and Cryptography (to appear)."},{"key":"29","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"},{"key":"30","doi-asserted-by":"publisher","first-page":"82","DOI":"10.2307\/1989993","article-title":"Maximal orders in rational cyclic algebras of composite degree","volume":"46","author":"Perlis, Sam","year":"1939","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2001-70-236\/S0025-5718-00-01283-7\/S0025-5718-00-01283-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-236\/S0025-5718-00-01283-7\/S0025-5718-00-01283-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,8]],"date-time":"2024-12-08T10:35:34Z","timestamp":1733654134000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-236\/S0025-5718-00-01283-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,10,17]]},"references-count":30,"journal-issue":{"issue":"236","published-print":{"date-parts":[[2001,10]]}},"alternative-id":["S0025-5718-00-01283-7"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-00-01283-7","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,10,17]]}}}