{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T13:18:15Z","timestamp":1776863895074,"version":"3.51.2"},"reference-count":23,"publisher":"American Mathematical Society (AMS)","issue":"213","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n If\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is an odd prime, the pseudosquare\n \n \n \n \n L<\/mml:mi>\n p<\/mml:mi>\n <\/mml:msub>\n L_p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is defined to be the least positive nonsquare integer such that\n \n \n \n \n \n L<\/mml:mi>\n p<\/mml:mi>\n <\/mml:msub>\n \n \u2261\n \n <\/mml:mo>\n 1<\/mml:mn>\n \n (<\/mml:mo>\n mod<\/mml:mi>\n \n 8<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n L_p\\equiv 1\\pmod {8}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and the Legendre symbol\n \n \n \n \n (<\/mml:mo>\n \n L<\/mml:mi>\n p<\/mml:mi>\n <\/mml:msub>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n q<\/mml:mi>\n )<\/mml:mo>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n (L_p\/q)=1<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for all odd primes\n \n \n \n \n q<\/mml:mi>\n \n \u2264\n \n <\/mml:mo>\n p<\/mml:mi>\n <\/mml:mrow>\n q\\le p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . In this paper we first discuss the connection between pseudosquares and primality testing. We then describe a new numerical sieving device which was used to extend the table of known pseudosquares up to\n \n \n \n \n L<\/mml:mi>\n \n 271<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n L_{271}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We also present several numerical results concerning the growth rate of the pseudosquares, results which so far confirm that\n \n \n \n \n \n L<\/mml:mi>\n p<\/mml:mi>\n <\/mml:msub>\n ><\/mml:mo>\n \n e<\/mml:mi>\n \n \n p<\/mml:mi>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:msqrt>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n L_p> e^{\\sqrt {p\/2}}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , an inequality that must hold under the extended Riemann Hypothesis.\n <\/p>","DOI":"10.1090\/s0025-5718-96-00678-3","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:13:45Z","timestamp":1027707225000},"page":"361-372","source":"Crossref","is-referenced-by-count":15,"title":["Some results on pseudosquares"],"prefix":"10.1090","volume":"65","author":[{"given":"R.","family":"Lukes","sequence":"first","affiliation":[]},{"given":"C.","family":"Patterson","sequence":"additional","affiliation":[]},{"given":"H.","family":"Williams","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1996]]},"reference":[{"issue":"1","key":"1","doi-asserted-by":"publisher","first-page":"173","DOI":"10.2307\/2006975","article-title":"On distinguishing prime numbers from composite numbers","volume":"117","author":"Adleman, Leonard M.","year":"1983","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"key":"2","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0090185","volume-title":"Primality testing and abelian varieties over finite fields","volume":"1512","author":"Adleman, Leonard M.","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/3540553088"},{"issue":"191","key":"3","doi-asserted-by":"publisher","first-page":"355","DOI":"10.2307\/2008811","article-title":"Explicit bounds for primality testing and related problems","volume":"55","author":"Bach, Eric","year":"1990","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"203","key":"4","doi-asserted-by":"publisher","first-page":"69","DOI":"10.2307\/2152936","article-title":"Statistical evidence for small generating sets","volume":"61","author":"Bach, Eric","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"5","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/BF01228507","article-title":"Sieve algorithms for perfect power testing","volume":"9","author":"Bach, Eric","year":"1993","journal-title":"Algorithmica","ISSN":"https:\/\/id.crossref.org\/issn\/0178-4617","issn-type":"print"},{"key":"6","unstructured":"N. G. W. H. Beeger, Sur la d\u00e9composition de grands nombres, Nieuw Arch. Wisk. (2) 16 (1929\/30), 37\u201342."},{"key":"7","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1017\/S0370164600012281","article-title":"On the reciprocation of certain matrices","volume":"59","author":"Collar, A. R.","year":"1939","journal-title":"Proc. Roy. Soc. Edinburgh","ISSN":"https:\/\/id.crossref.org\/issn\/0370-1646","issn-type":"print"},{"key":"8","doi-asserted-by":"crossref","unstructured":"A. Cobham, The recognition problem for perfect squares, Proc. 1966 IEEE Symposium on Switching and Automata Theory, IEEE Press, 1966, pp. 78\u201387.","DOI":"10.1109\/SWAT.1966.30"},{"key":"9","doi-asserted-by":"crossref","unstructured":"N. D. Bronson and D. A. Buell, Congruential sieves on FPGA computers, Proc. Sympos. Appl. Math., vol. 48, 1994, pp. 547\u2013551.","DOI":"10.1090\/psapm\/048\/1314888"},{"key":"10","doi-asserted-by":"crossref","unstructured":"M. Hall, Quadratic residues in factorization, Bull. Amer. Math. Soc. 39 (1933), 758\u2013763.","DOI":"10.1090\/S0002-9904-1933-05730-0"},{"key":"11","unstructured":"M. Kraitchik, Recherches sur la th\u00e9orie des nombres, Gauthier-Villars, Paris, 1924."},{"key":"12","unstructured":"\\bysame, R\u00e9cherches sur la th\u00e9orie des nombres. I. II, Gauthier-Villars, Paris, 1929."},{"key":"13","unstructured":"\\bysame, Factorisation es grands nombres, Sphinx 1 (1931), 35\u201337."},{"issue":"2","key":"14","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1137\/0211029","article-title":"On primality tests","volume":"11","author":"Lehmann, Daniel J.","year":"1982","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"15","doi-asserted-by":"crossref","unstructured":"D. H. Lehmer, A fallacious principle in the theory of numbers, Bull. Amer. Math. Soc. 36 (1930), 847\u2013850.","DOI":"10.1090\/S0002-9904-1930-05077-6"},{"key":"16","doi-asserted-by":"publisher","first-page":"611","DOI":"10.2307\/1968946","article-title":"On Frobeniusean algebras. I","volume":"40","author":"Nakayama, Tadasi","year":"1939","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"key":"17","isbn-type":"print","volume-title":"A history of computing in the twentieth century","year":"1980","ISBN":"https:\/\/id.crossref.org\/isbn\/0124916503"},{"key":"18","doi-asserted-by":"publisher","first-page":"433","DOI":"10.2307\/2004491","article-title":"Integer sequences having prescribed quadratic character","volume":"24","author":"Lehmer, D. H.","year":"1970","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"19","unstructured":"C. Patterson, A 538 billion integer per second sieve, Proc. 1991 Canad. Conf. on Electrical and Computer Engineering, 1991, pp. 13.1.1\u201313.1.4."},{"key":"20","unstructured":"\\bysame, The derivation of a high speed sieve device, Ph.D. Thesis, Dept. of Computer Science, University of Calgary, Calgary, Canada, 1991."},{"key":"21","first-page":"267","article-title":"Systematic examination of Littlewood\u2019s bounds on \ud835\udc3f(1,\ud835\udf12)","author":"Shanks, Daniel","year":"1973"},{"key":"22","doi-asserted-by":"crossref","unstructured":"A. J. Stephens and H. C. Williams, An open architecture number sieve, Number Theory and Cryptography (Sydney, 1989), London Math. Soc. Lecture Note Ser., vol. 154, Cambridge Univ. Press, Cambridge, 1990, pp. 38\u201375.","DOI":"10.1017\/CBO9781107325838.005"},{"key":"23","first-page":"127","article-title":"Primality testing on a computer","volume":"5","author":"Williams, H. C.","year":"1978","journal-title":"Ars Combin.","ISSN":"https:\/\/id.crossref.org\/issn\/0381-7032","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1996-65-213\/S0025-5718-96-00678-3\/S0025-5718-96-00678-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1996-65-213\/S0025-5718-96-00678-3\/S0025-5718-96-00678-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:02:34Z","timestamp":1776718954000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1996-65-213\/S0025-5718-96-00678-3\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"references-count":23,"journal-issue":{"issue":"213","published-print":{"date-parts":[[1996,1]]}},"alternative-id":["S0025-5718-96-00678-3"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-96-00678-3","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":[[1996]]}}}