The distribution of Lucas and elliptic pseudoprimes

Gordon, Daniel M.; Pomerance, Carl

doi:10.1090/S0025-5718-1991-1094951-8

The distribution of Lucas and elliptic pseudoprimes
HTML articles powered by AMS MathViewer

by Daniel M. Gordon and Carl Pomerance PDF

Math. Comp. 57 (1991), 825-838 Request permission

Corrigendum: Math. Comp. 60 (1993), 877.
Corrigendum: Math. Comp. 60 (1993), 877.

Abstract:

Let $\mathcal {L}(x)$ denote the counting function for Lucas pseudoprimes, and $\mathcal {E}(x)$ denote the elliptic pseudoprime counting function. We prove that, for large x, $\mathcal {L}(x) \leq xL{(x)^{ - 1/2}}$ and $\mathcal {E}(x) \leq xL{(x)^{ - 1/3}}$, where \[ L(x) = \exp (\log x\log \log \log x/\log \log x).\]

References

Robert Baillie and Samuel S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391–1417. MR 583518, DOI 10.1090/S0025-5718-1980-0583518-6
R. Balasubramanian and M. Ram Murty, Elliptic pseudoprimes. II, Séminaire de Théorie des Nombres, Paris 1988–1989, Progr. Math., vol. 91, Birkhäuser Boston, Boston, MA, 1990, pp. 13–25. MR 1104697
E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI 10.1090/S0025-5718-1970-0276200-X

Su di un metodo per la risoluzione in numeri interi dell’ equazione

46

A lower bound for the counting function of Lucas pseudoprimes

41

Daniel M. Gordon, On the number of elliptic pseudoprimes, Math. Comp. 52 (1989), no. 185, 231–245. MR 946604, DOI 10.1090/S0025-5718-1989-0946604-2
Rajiv Gupta and M. Ram Murty, Primitive points on elliptic curves, Compositio Math. 58 (1986), no. 1, 13–44. MR 834046
G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
Burton W. Jones, The Arithmetic Theory of Quadratic Forms, Carcus Monograph Series, no. 10, Mathematical Association of America, Buffalo, N.Y., 1950. MR 0037321
Serge Lang, Elliptic curves: Diophantine analysis, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 231, Springer-Verlag, Berlin-New York, 1978. MR 518817
H. W. Lenstra Jr., Elliptic curves and number-theoretic algorithms, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Berkeley, Calif., 1986) Amer. Math. Soc., Providence, RI, 1987, pp. 99–120. MR 934218
Carl Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), no. 156, 587–593. MR 628717, DOI 10.1090/S0025-5718-1981-0628717-0
Carl Pomerance, A new lower bound for the pseudoprime counting function, Illinois J. Math. 26 (1982), no. 1, 4–9. MR 638549
Carl Pomerance, Two methods in elementary analytic number theory, Number theory and applications (Banff, AB, 1988) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 265, Kluwer Acad. Publ., Dordrecht, 1989, pp. 135–161. MR 1123073
René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI 10.1090/S0025-5718-1985-0777280-6
Morgan Ward, Memoir on elliptic divisibility sequences, Amer. J. Math. 70 (1948), 31–74. MR 23275, DOI 10.2307/2371930