Summary: 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 \(\mathrm{gcd}(b,N)=1\). D. M. Gordon [in: Théorie des nombres, C. R. Conf. Int., Québec/Can. 1987, 290–305 (1989; Zbl 0684.10006)] 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. H. Silverman [Acta Arith. 155, No. 3, 233–246 (2012; Zbl 1304.11047)] 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.