Strongly nonzero points and elliptic pseudoprimes

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) equivalent to 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.