Some results on pseudosquares

Lukes, R.; Patterson, C.; Williams, H.

doi:10.1090/S0025-5718-96-00678-3

Some results on pseudosquares
HTML articles powered by AMS MathViewer

by R. F. Lukes, C. D. Patterson and H. C. Williams PDF

Math. Comp. 65 (1996), 361-372 Request permission

Abstract:

If $p$ is an odd prime, the pseudosquare $L_p$ is defined to be the least positive nonsquare integer such that $L_p\equiv 1\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

Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), no. 1, 173–206. MR 683806, DOI 10.2307/2006975
Leonard M. Adleman and Ming-Deh A. Huang, Primality testing and abelian varieties over finite fields, Lecture Notes in Mathematics, vol. 1512, Springer-Verlag, Berlin, 1992. MR 1176511, DOI 10.1007/BFb0090185
Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, DOI 10.1090/S0025-5718-1990-1023756-8
Eric Bach and Lorenz Huelsbergen, Statistical evidence for small generating sets, Math. Comp. 61 (1993), no. 203, 69–82. MR 1195432, DOI 10.1090/S0025-5718-1993-1195432-5
Eric Bach and Jonathan Sorenson, Sieve algorithms for perfect power testing, Algorithmica 9 (1993), no. 4, 313–328. MR 1208565, DOI 10.1007/BF01228507
N. G. W. H. Beeger, Sur la décomposition de grands nombres, Nieuw Arch. Wisk. (2) 16 (1929/30), 37–42.
A. R. Collar, On the reciprocation of certain matrices, Proc. Roy. Soc. Edinburgh 59 (1939), 195–206. MR 8, DOI 10.1017/S0370164600012281
A. Cobham, The recognition problem for perfect squares, Proc. 1966 IEEE Symposium on Switching and Automata Theory, IEEE Press, 1966, pp. 78–87.
N. D. Bronson and D. A. Buell, Congruential sieves on FPGA computers, Proc. Sympos. Appl. Math., vol. 48, 1994, pp. 547–551.
M. Hall, Quadratic residues in factorization, Bull. Amer. Math. Soc. 39 (1933), 758–763.
M. Kraitchik, Recherches sur la théorie des nombres, Gauthier-Villars, Paris, 1924.
—, Récherches sur la théorie des nombres. I. II, Gauthier-Villars, Paris, 1929.
—, Factorisation es grands nombres, Sphinx 1 (1931), 35–37.
Daniel J. Lehmann, On primality tests, SIAM J. Comput. 11 (1982), no. 2, 374–375. MR 652910, DOI 10.1137/0211029
D. H. Lehmer, A fallacious principle in the theory of numbers, Bull. Amer. Math. Soc. 36 (1930), 847–850.
Tadasi Nakayama, On Frobeniusean algebras. I, Ann. of Math. (2) 40 (1939), 611–633. MR 16, DOI 10.2307/1968946
N. Metropolis, J. Howlett, and Gian-Carlo Rota (eds.), A history of computing in the twentieth century, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. A collection of essays. MR 584927
D. H. Lehmer, Emma Lehmer, and Daniel Shanks, Integer sequences having prescribed quadratic character, Math. Comp. 24 (1970), 433–451. MR 271006, DOI 10.1090/S0025-5718-1970-0271006-X
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.
—, The derivation of a high speed sieve device, Ph.D. Thesis, Dept. of Computer Science, University of Calgary, Calgary, Canada, 1991.
Daniel Shanks, Systematic examination of Littlewood’s bounds on $L(1,\,\chi )$, Analytic number theory (Proc. Sympos. Pure Math., Vol. XXIV, St. Louis Univ., St. Louis, Mo., 1972) Amer. Math. Soc., Providence, R.I., 1973, pp. 267–283. MR 0337827
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.
H. C. Williams, Primality testing on a computer, Ars Combin. 5 (1978), 127–185. MR 504864