In computational number theory, distinguishing prime numbers from composite numbers is a foundational challenge. The simplest primality tests rely on Fermat's Little Theorem, which states that if $n$ is prime, then $a^{n-1} \equiv 1 \pmod n$ for any integer $a$ coprime to $n$. However, certain composite numbers—known as Carmichael numbers—act as mathematical imposters, satisfying this condition for all choices of $a$.
To understand why these imposters exist, we turn to the classical Korselt criterion (1899). It provides a purely structural explanation: a composite number $n$ is a Carmichael number if and only if it is square-free and, for every prime factor $p$ of $n$, the term $(p-1)$ divides $(n-1)$. This algebraic alignment allows the composite number to perfectly mimic prime behavior across the multiplicative groups of its modular components.
In recent decades, the focus of primality testing has expanded from the multiplicative group of integers to the richer geometric structure of elliptic curves. But just as classical primality tests have their imposters, elliptic curve tests face their own: elliptic pseudoprimes and elliptic Carmichael numbers.
The Challenge of the Elliptic Setting
When we move from standard modular arithmetic to an elliptic curve $E$ defined over a finite field $\mathbb{F}_p$, the group structure changes. Instead of a fixed group order of $p-1$, the number of points on the curve is given by: $$\#E(\mathbb{F}_p) = p + 1 - a_p$$ where $a_p$ is the trace of Frobenius, bounded by Hasse's theorem ($|a_p| \le 2\sqrt{p}$).
Because the group order $\#E(\mathbb{F}_p)$ varies depending on the specific curve $E$, defining an analogue to the Korselt criterion becomes significantly more complex. For a composite number $n$ to act as an elliptic Carmichael number, it must mimic prime behavior across all points on a given curve. This requires the local group orders at each prime factor to align perfectly with a global property of $n$, a condition that is far more difficult to satisfy than the classical criterion.
The Role of Anomalous Primes
To resolve how a composite number can satisfy these stringent conditions, Babinkostova et al. in their work on Anomalous Primes and the Elliptic Korselt Criterion investigated the exact relationship between a curve's trace of Frobenius and the prime factors of an elliptic imposter. They discovered that these numbers are almost always constructed from an exceedingly rare class of primes known as anomalous primes.
An anomalous prime for a given elliptic curve $E$ is a prime $p$ where the number of points on the curve is exactly equal to the prime itself: $$\#E(\mathbb{F}_p) = p$$ This occurs precisely when the trace of Frobenius $a_p = 1$.
Why does this property unlock the elliptic Korselt criterion? When $\#E(\mathbb{F}_p) = p$, the local group structure simplifies dramatically. The divisibility requirements that allow a composite number to pass as a prime become mathematically permissive only under this constraint. The authors demonstrated that for certain formulations of the elliptic Korselt criterion, having anomalous prime factors is not just a curiosity, but a structural necessity.
A Formal Taxonomy of Elliptic Imposters
Building on this structural foundation, deeper mathematical frameworks have been developed to classify these elusive numbers. In On Types of Elliptic Pseudoprimes, Babinkostova et al. formalized new, stricter categories of mathematical imposters, specifically defining Euler elliptic Carmichael numbers and strong elliptic Carmichael numbers.
These definitions extend classical pseudoprime concepts to capture varying degrees of prime-mimicking behavior across the entire algebraic structure of the curve. The authors established the necessary and sufficient conditions required to identify these numbers, effectively delivering a modernized, elliptic analogue to Korselt's original 1899 breakthrough.
Furthermore, the authors conducted a density analysis of these elliptic Korselt numbers. Because these numbers rely so heavily on the product of anomalous primes, their distribution is exceptionally sparse. By employing probabilistic arguments and number-theoretic estimations, the authors analyzed their distribution within the number system, demonstrating that they are far rarer than their classical Carmichael counterparts.
This line of research continues a long-standing tradition in number theory dedicated to uncovering the distribution patterns and structural properties of specific integer classes—a pursuit reflected in foundational algebraic investigations such as those compiled in the Journal of the Australian Mathematical Society. By mapping the classical rules of divisibility onto the geometric landscape of elliptic curves, researchers have revealed the precise conditions under which composite numbers can successfully wear the mask of a prime.
Key Foundational Work
Anomalous primes and the elliptic Korselt criterion (2019) — contributed 3 concept elements to this direction.
JAZ volume 15 issue 2 Cover and Front matter (1973) — contributed 2 concept elements to this direction.