Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

The distribution of Lucas and elliptic pseudoprimes


Authors: Daniel M. Gordon and Carl Pomerance
Journal: Math. Comp. 57 (1991), 825-838
MSC: Primary 11N80; Secondary 11B39, 11G05, 11Y11
DOI: https://doi.org/10.1090/S0025-5718-1991-1094951-8
Corrigendum: Math. Comp. 60 (1993), 877.
Corrigendum: Math. Comp. 60 (1993), 877.
MathSciNet review: 1094951
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

$\displaystyle L(x) = \exp (\log x\log \log \log x/\log \log x).$


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

  • [1] R. Baillie and S. S. Wagstaff, Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), 1391-1417. MR 583518 (81j:10005)
  • [2] R. Balasubramanian and M. Ram Murty, Elliptic pseudoprimes. II, Seminaire de theorie des nombres, Paris 1988-89 (C. Goldstein, ed.), Birkhäuser, 1990, pp. 13-25. MR 1104697 (92f:11076)
  • [3] E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713-735. MR 0276200 (43:1948)
  • [4] G. Cornacchia, Su di un metodo per la risoluzione in numeri interi dell' equazione $ \sum _{h = 0}^n{C_h}{x^{n - h}}{y^h} = P$, Giornale di Matematiche di Battaglini 46 (1908), 33-90.
  • [5] P. Erdös, P. Kiss, and A. Sárközy, A lower bound for the counting function of Lucas pseudoprimes, Math. Comp. 41 (1988), 315-323.
  • [6] D. M. Gordon, Pseudoprimes on elliptic curves, Math. Comp. 52 (1989), 231-245. MR 946604 (89f:11169)
  • [7] R. Gupta and M. Ram Murty, Primitive points on elliptic curves, Compositio Math. 58 (1986), 13-44. MR 834046 (87h:11050)
  • [8] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., Clarendon Press, Oxford, 1979. MR 568909 (81i:10002)
  • [9] B. W. Jones, The arithmetic theory of quadratic forms, Math. Assoc. Amer., Baltimore, MD, 1950. MR 0037321 (12:244a)
  • [10] S. Lang, Elliptic curves: Diophantine analysis, Springer-Verlag, Heidelberg, 1978. MR 518817 (81b:10009)
  • [11] H. W. Lenstra, Jr., Elliptic curves and number-theoretic algorithms, Proc. Internat. Congr. Math. (Berkeley, 1986), Amer. Math. Soc., Providence, RI, 1987, pp. 99-120. MR 934218 (89d:11114)
  • [12] C. Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587-593. MR 628717 (83k:10009)
  • [13] -, A new lower bound for the pseudoprime counting function, Illinois J. Math. 26 (1982), 4-9. MR 638549 (83h:10012)
  • [14] -, Two methods in elementary analytic number theory, Number Theory and Applications (R. A. Mollin, ed.), Kluwer, The Netherlands, 1989, pp. 135-161. MR 1123073 (92j:11107)
  • [15] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 44 (1985), 483-494. MR 777280 (86e:11122)
  • [16] M. Ward, Memoir on elliptic divisibility sequences, Amer. J. Math. 70 (1948), 31-74. MR 0023275 (9:332j)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11N80, 11B39, 11G05, 11Y11

Retrieve articles in all journals with MSC: 11N80, 11B39, 11G05, 11Y11


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1991-1094951-8
Article copyright: © Copyright 1991 American Mathematical Society

American Mathematical Society