Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Some Results on Pseudosquares

Authors: R. F. Lukes, C. D. Patterson and H. C. Williams
Journal: Math. Comp. 65 (1996), 361-372
MSC (1991): Primary 11A51, 11Y11, 11-04, 11Y55
Supplement: Additional information related to this article.
MathSciNet review: 1322892
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: If $p$ is an odd prime, the pseudosquare $L_p$ is defined to be the least positive nonsquare integer such that $L_p\equiv1\pmod{8}$ and the Legendre symbol $(L_p/q)=1$ for all odd primes $q\le p$. 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 $L_{271}$. We also present several numerical results concerning the growth rate of the pseudosquares, results which so far confirm that $L_p> e^{\sqrt{p/2}}$, an inequality that must hold under the extended Riemann Hypothesis.

References [Enhancements On Off] (What's this?)

  • 1 L. M. Adleman, C. Pomerance, and R. S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983),173--206. MR 84e:10008
  • 2 L. M. Adleman and M.-D. Huang, Primality testing and Abelian varieties over finite fields, Lecture Notes in Math., vol. 1512, Springer-Verlag, Berlin, 1992. MR 93g:11128
  • 3 Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), 355--380. MR 91m:11096
  • 4 Eric Bach and L. Huelsbergen, Statistical evidence for small generating sets, Math. Comp. 61 (1993), 69--82. MR 93k:11089
  • 5 Eric Bach and J. Sorenson, Sieve algorithms for perfect power testing, Algorithmica 9 (1993), 313--328. MR 94d:11103
  • 6 N. G. W. H. Beeger, Sur la décomposition de grands nombres, Nieuw Arch. Wisk. (2) 16 (1929/30), 37--42.
  • 7 ------, Note sur la factorisation de quelques grands nombres, Arch. Inst. Grand-Ducal Luxembourg Sect. Sci. Nat. Phys. Math. 16 (1946), 93--95. MR 8:134
  • 8 A. Cobham, The recognition problem for perfect squares, Proc. 1966 IEEE Symposium on Switching and Automata Theory, IEEE Press, 1966, pp. 78--87.
  • 9 N. D. Bronson and D. A. Buell, Congruential sieves on FPGA computers, Proc. Sympos. Appl. Math., vol. 48, 1994, pp. 547--551.
  • 10 M. Hall, Quadratic residues in factorization, Bull. Amer. Math. Soc. 39 (1933), 758--763.
  • 11 M. Kraitchik, Recherches sur la théorie des nombres, Gauthier-Villars, Paris, 1924.
  • 12 ------, Récherches sur la théorie des nombres. I. II, Gauthier-Villars, Paris, 1929.
  • 13 ------, Factorisation es grands nombres, Sphinx 1 (1931), 35--37.
  • 14 D. J. Lehmann, On primality tests, SIAM J. Comput. 11 (1982), 374--375. MR 83i:10006
  • 15 D. H. Lehmer, A fallacious principle in the theory of numbers, Bull. Amer. Math. Soc. 36 (1930), 847--850.
  • 16 ------, A sieve problem on pseudo-squares, MTAC 8 (1954), 241--242. MR 16:113
  • 17 ------, A history of the sieve process, A History of Computing in the Twentieth Century, Academic Press, New York, 1980, pp. 445--456. MR 81i:68002
  • 18 D. H. Lehmer, E. Lehmer, and D. Shanks, Integer sequences having prescribed quadratic character, Math. Comp. 24 (1970), 433--451. MR 42:5889
  • 19 C. Patterson, A $538$ billion integer per second sieve, Proc. 1991 Canad. Conf. on Electrical and Computer Engineering, 1991, pp. 13.1.1--13.1.4.
  • 20 ------, The derivation of a high speed sieve device, Ph.D. Thesis, Dept. of Computer Science, University of Calgary, Calgary, Canada, 1991.
  • 21 D. Shanks, Systematic examination of Littlewood's bounds on $L(1,\chi)$, Proc. Sympos. Pure Math., vol. 24, Amer. Math. Soc., Providence, RI, 1973, pp. 267--283. MR 49:2596
  • 22 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--75. CMP 90:13
  • 23 H. C. Williams, Primality testing on a computer, Ars Combin. 5 (1978), 127--185. MR 80d:10002

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11A51, 11Y11, 11-04, 11Y55

Retrieve articles in all journals with MSC (1991): 11A51, 11Y11, 11-04, 11Y55

Additional Information

R. F. Lukes
Affiliation: Department of Computer Science, University of Manitoba, Winnipeg, Manitoba, Canada R3T 2N2

C. D. Patterson
Affiliation: Xilinx Development Corporation, 52 Mortonhall Gate, Edinburgh EH16 6TJ, Scotland

H. C. Williams
Affiliation: Department of Computer Science, University of Manitoba, Winnipeg, Manitoba, Canada R3T 2N2

Received by editor(s): August 23, 1993
Received by editor(s) in revised form: April 8, 1994
Additional Notes: Research of the third author supported by NSERC of Canada grant #A7649
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society