Strongly nonzero points and elliptic pseudoprimes

Babinkostova, Liljana; Fillmore, Dylan; Lamkin, Philip; Lin, Alice; Yost-Wolff, Calvin L.

doi:10.2140/involve.2021.14.65

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

Strongly nonzero points and elliptic pseudoprimes

Liljana Babinkostova, Dylan Fillmore, Philip Lamkin, Alice Lin and Calvin L. Yost-Wolff

Vol. 14 (2021), No. 1, 65–88

DOI: 10.2140/involve.2021.14.65

Abstract

Efficiently distinguishing prime and composite numbers is one of the fundamental problems in number theory. A Fermat pseudoprime is a composite number $N$ which satisfies Fermat’s little theorem for a specific base $b$ : $b^{N - 1} \equiv 1 mod N$ . A Carmichael number $N$ is a Fermat pseudoprime for all $b$ with $gcd (b, N) = 1$ . D. Gordon (1987) introduced analogues of Fermat pseudoprimes and Carmichael numbers for elliptic curves with complex multiplication (CM): elliptic pseudoprimes, strong elliptic pseudoprimes and elliptic Carmichael numbers. It has previously been shown that no CM curve has a strong elliptic Carmichael number. We give bounds on the fraction of points on a curve for which a fixed composite number $N$ can be a strong elliptic pseudoprime. J. Silverman (2012) extended Gordon’s notion of elliptic pseudoprimes and elliptic Carmichael numbers to arbitrary elliptic curves. We provide probabilistic bounds for whether a fixed composite number $N$ is an elliptic Carmichael number for a randomly chosen elliptic curve.

Keywords

elliptic curves, pseudoprimes, strongly nonzero elliptic pseudoprimes, elliptic Carmichael numbers

Mathematical Subject Classification 2010

Primary: 14H52, 14K22

Secondary: 11N25, 11G07, 11G20, 11B99

Supplementary material

Proofs of Theorems 4.7 and 4.20

Milestones

Received: 1 October 2019

Revised: 12 August 2020

Accepted: 29 September 2020

Published: 4 March 2021

Communicated by Kenneth S. Berenhaut

Authors

Liljana Babinkostova
Department of Mathematics Boise State University Boise, ID United States

Dylan Fillmore
Department of Mathematics University of South Carolina Columbia, SC United States

Philip Lamkin
Department of Mathematics Carnegie Mellon University Pittsburgh, PA United States

Alice Lin
Department of Mathematics Princeton University Princeton, NJ United States

Calvin L. Yost-Wolff
Department of Mathematics Massachusetts Institute of Technology Cambridge, MA United States

Vol. 14, No. 1, 2021