Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



On the existence and non-existence of elliptic pseudoprimes

Author: Siguna Müller
Journal: Math. Comp. 79 (2010), 1171-1190
MSC (2000): Primary 11Y11; Secondary 11Y40, 11A51
Published electronically: October 16, 2009
MathSciNet review: 2600561
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In a series of papers, D. Gordon and C. Pomerance demonstrated that pseudoprimes on elliptic curves behave in many ways very similar to pseudoprimes related to Lucas sequences. In this paper we give an answer to a challenge that was posted by D. Gordon in 1989. The challenge was to either prove that a certain composite $ N \equiv 1 \bmod 4$ did not exist, or to explicitly calculate such a number. In this paper, we both present such a specific composite (for Gordon's curve with CM by $ \mathbb{Q}(\sqrt{-7})$), as well as a proof of the non-existence (for curves with CM by $ \mathbb{Q}(\sqrt{-3}$)). We derive some criteria for the group structure of CM curves that allow testing for all composites, including $ N \equiv 3 \bmod 4$ which had been excluded by Gordon. This gives rise to another type of examples of composites where strong elliptic pseudoprimes are not Euler elliptic pseudoprimes.

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y11, 11Y40, 11A51

Retrieve articles in all journals with MSC (2000): 11Y11, 11Y40, 11A51

Additional Information

Siguna Müller
Affiliation: Department of Mathematics, RH 311, University of Wyoming, Laramie, Wyoming 82071

Received by editor(s): August 28, 2008
Received by editor(s) in revised form: December 4, 2008, and March 4, 2009
Published electronically: October 16, 2009
Article copyright: © Copyright 2009 American Mathematical Society

American Mathematical Society