{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T22:47:42Z","timestamp":1776725262867,"version":"3.51.2"},"reference-count":27,"publisher":"American Mathematical Society (AMS)","issue":"234","license":[{"start":{"date-parts":[[2001,6,12]],"date-time":"2001-06-12T00:00:00Z","timestamp":992304000000},"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":"

\n Let\n \n \n \n \n m<\/mml:mi>\n =<\/mml:mo>\n p<\/mml:mi>\n l<\/mml:mi>\n <\/mml:mrow>\n m= pl<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n be a product of two distinct primes\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and\n \n \n \n l<\/mml:mi>\n l<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We show that for almost all exponents\n \n \n \n e<\/mml:mi>\n e<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n with\n \n \n \n \n gcd<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n (<\/mml:mo>\n e<\/mml:mi>\n ,<\/mml:mo>\n \n \u03c6\n \n <\/mml:mi>\n (<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n )<\/mml:mo>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n \\operatorname {gcd} (e, \\varphi (m))= 1<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n the RSA pairs\n \n \n \n \n (<\/mml:mo>\n x<\/mml:mi>\n ,<\/mml:mo>\n \n x<\/mml:mi>\n e<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n (x, x^e)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n are uniformly distributed modulo\n \n \n \n m<\/mml:mi>\n m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n when\n \n \n \n x<\/mml:mi>\n x<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n runs through\n <\/p>\n

\n the group of units\n \n \n \n \n \n Z<\/mml:mi>\n <\/mml:mrow>\n m<\/mml:mi>\n \n \u2217\n \n <\/mml:mo>\n <\/mml:msubsup>\n \\mathbb {Z}_m^*<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n modulo\n \n \n \n m<\/mml:mi>\n m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n (that is, as in the classical RSA scheme);\n <\/p>\n

\n the set of\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -products\n \n \n \n \n x<\/mml:mi>\n =<\/mml:mo>\n \n a<\/mml:mi>\n \n \n i<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:msub>\n \n \u22ef\n \n <\/mml:mo>\n \n a<\/mml:mi>\n \n \n i<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:mrow>\n x = a_{i_1}\\cdots a_{i_k}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n ,\n \n \n \n \n 1<\/mml:mn>\n \n \u2264\n \n <\/mml:mo>\n \n i<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ><\/mml:mo>\n \n \u22ef\n \n <\/mml:mo>\n ><\/mml:mo>\n \n i<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n \n \u2264\n \n <\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n 1 \\le i_1 > \\cdots > i_k \\le n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , where\n \n \n \n \n \n a<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n \u22ef\n \n <\/mml:mo>\n ,<\/mml:mo>\n \n a<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n \n \u2208\n \n <\/mml:mo>\n \n \n Z<\/mml:mi>\n <\/mml:mrow>\n m<\/mml:mi>\n \n \u2217\n \n <\/mml:mo>\n <\/mml:msubsup>\n <\/mml:mrow>\n a_1, \\cdots , a_n \\in \\mathbb {Z}_m^*<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n are selected at random (that is, as in the recently introduced RSA scheme with precomputation).\n <\/p>\n

These results are based on some new bounds of exponential sums.<\/p>","DOI":"10.1090\/s0025-5718-00-01274-6","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:17:46Z","timestamp":1027707466000},"page":"801-808","source":"Crossref","is-referenced-by-count":3,"title":["On the uniformity of distribution of the RSA pairs"],"prefix":"10.1090","volume":"70","author":[{"given":"Igor","family":"Shparlinski","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2000,6,12]]},"reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, \u2018Generating hard instances of lattice problems\u2019, Electronic Colloq. on Comp. Compl., Univ. of Trier, TR96-007 (1996), 1\u201329.","DOI":"10.1145\/237814.237838"},{"key":"2","doi-asserted-by":"crossref","unstructured":"W. Banks, F. Griffin, D. Lieman and I. E. Shparlinski, \u2018Non-linear complexity of the Naor-Reingold pseudo-random function\u2019, Proc. the 2nd Intern. Conf. on Information Security and Cryptology, Seoul, 1999, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, (to appear).","DOI":"10.1007\/10719994_5"},{"issue":"2","key":"3","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"},{"key":"4","doi-asserted-by":"crossref","unstructured":"V. Boyko, M. Peinado and R. Venkatesan, \u2018Speeding up discrete log and factoring based schemes via precomputations\u2019, Proc. of Eurocrypt\u201998, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1403 (1998), 221\u2013234.","DOI":"10.1007\/BFb0054129"},{"key":"5","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)."},{"key":"6","doi-asserted-by":"crossref","unstructured":"R. Canetti, J. B. Friedlander and I. E. Shparlinski, \u2018On certain exponential sums and the distribution of Diffie\u2013Hellman triples\u2019, J. London Math. Soc., (1999), 799\u2013812.","DOI":"10.1112\/S002461079900736X"},{"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","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0093404","volume-title":"Sequences, discrepancies and applications","volume":"1651","author":"Drmota, Michael","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/3540626069"},{"key":"9","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":"10","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":"11","unstructured":"J. B. Friedlander and I. E. Shparlinski, \u2018On the distribution of the power generator\u2019, Math. Comp., (to appear)."},{"key":"12","doi-asserted-by":"crossref","unstructured":"F. Griffin and I. E. Shparlinski, \u2018On the linear complexity of the Naor-Reingold pseudo-random function\u2019, Proc. 2nd Intern. Conf. on Information and Communication Security, Sydney, 1999, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1726 (1999), 301\u2013308.","DOI":"10.1007\/978-3-540-47942-0_25"},{"key":"13","unstructured":"F. Griffin and I. E. Shparlinski, \u2018On the linear complexity profile of the power generator\u2019, Trans. IEEE Inform. Theory (to appear)."},{"issue":"4","key":"14","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s001459900012","article-title":"Efficient cryptographic schemes provably as secure as subset sum","volume":"9","author":"Impagliazzo, Russell","year":"1996","journal-title":"J. Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"key":"15","isbn-type":"print","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","ISBN":"https:\/\/id.crossref.org\/isbn\/0821801554"},{"key":"16","series-title":"Princeton Computer Science Notes","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1515\/9780691206844","volume-title":"Pseudorandomness and cryptographic applications","author":"Luby, Michael","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/0691025460"},{"key":"17","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":"18","doi-asserted-by":"crossref","unstructured":"M. Naor and O. Reingold, \u2018Number-theoretic constructions of efficient pseudo-random functions\u2019, Proc. 38th IEEE Symp. on Foundations of Comp. Sci., 1997, 458\u2013467.","DOI":"10.1109\/SFCS.1997.646134"},{"key":"19","doi-asserted-by":"crossref","unstructured":"M. Naor and O. Reingold, \u2018Synthesizers and their application to the parallel construction of pseudo-random functions\u2019, J. Comp. and Sys. Sci., 58 (1999), 336\u2013375.","DOI":"10.1006\/jcss.1998.1618"},{"key":"20","doi-asserted-by":"crossref","unstructured":"P. Nguyen, I. E. Shparlinski and J. Stern, \u2018Distribution of modular sums and the security of the server aided exponentiation\u2019, Preprint, 2000, 1\u201316.","DOI":"10.1007\/978-3-0348-8295-8_24"},{"key":"21","doi-asserted-by":"crossref","unstructured":"P. Nguyen and J. Stern, \u2018The hardness of the hidden subset sum problem and its cryptographic implications\u2019, Proc. CRYPTO\u201999, Santa Barbara, 1999, Springer-Verlag, Berlin, 1666 (1999), 31\u201346.","DOI":"10.1007\/3-540-48405-1_3"},{"key":"22","unstructured":"I. E. Shparlinski, \u2018On the uniformity of distribution of the Naor-Reingold pseudo-random number function\u2019, Finite Fields and Their Appl. (to appear)."},{"key":"23","unstructured":"I. E. Shparlinski, \u2018On the Naor-Reingold pseudo-random number generator from elliptic curves\u2019, Appl. Algebra in Engin., Commun. and Computing (to appear)."},{"key":"24","unstructured":"I. E. Shparlinski, \u2018On the linear complexity of the power generator\u2019, Designs, Codes and Cryptography, (to appear)."},{"key":"25","doi-asserted-by":"crossref","unstructured":"I. E. Shparlinski and J. H. Silverman, \u2018Linear complexity of the Naor\u2013Reingold pseudo-random number function from elliptic curves\u2019, Preprint, 1999, 1\u201314.","DOI":"10.1007\/s002000000023"},{"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"},{"key":"27","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"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2001-70-234\/S0025-5718-00-01274-6\/S0025-5718-00-01274-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-234\/S0025-5718-00-01274-6\/S0025-5718-00-01274-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T22:35:33Z","timestamp":1776724533000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-234\/S0025-5718-00-01274-6\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,6,12]]},"references-count":27,"journal-issue":{"issue":"234","published-print":{"date-parts":[[2001,4]]}},"alternative-id":["S0025-5718-00-01274-6"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-00-01274-6","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":[[2000,6,12]]}}}