Anomalous primes and the elliptic Korselt criterion

Liljana Babinkostova, Jackson Bahr, Y.h. Kim, Eric Neyman, Graham K. TaylorJournal of Number Theory 2019 · DOI · arXiv

Introduction

In the field of computational number theory, distinguishing between prime and composite numbers is a fundamental challenge. While Fermat’s Little Theorem provides a robust test for primality, it is famously "fooled" by Carmichael numbers—composite integers that satisfy the congruence $a^{n-1} \equiv 1 \pmod n$ for all integers $a$ coprime to $n$. The Korselt criterion provides a definitive characterization of these numbers: a composite integer $n$ is a Carmichael number if and only if it is squarefree and for every prime divisor $p$ of $n$, $(p-1)$ divides $(n-1)$.

As mathematical research has shifted toward elliptic curve cryptography and primality testing, the concept of pseudoprimes has been extended to the domain of elliptic curves. This paper investigates Type I elliptic Korselt numbers, a class of elliptic pseudoprimes, and reveals a profound connection to anomalous primes.

The Elliptic Korselt Criterion

Joseph Silverman previously introduced the Elliptic Korselt Criterion to identify composite numbers that mimic the behavior of primes relative to elliptic curve groups. For an elliptic curve $E$ over $\mathbb{Q}$, a squarefree composite integer $n = p_1 p_2 \dots p_m$ is a Type I elliptic Korselt number if it satisfies specific divisibility conditions involving the order of the curve over finite fields $\mathbb{F}_{p_i}$.

The authors focus on the "building blocks" of these numbers. Specifically, they examine the relationship between these composite numbers and anomalous primes—rare primes $p$ where the number of points on the elliptic curve $E(\mathbb{F}_p)$ is exactly $p$. In the language of the trace of Frobenius ($a_p$), a prime is anomalous for a curve $E$ if $a_p = 1$, since $|E(\mathbb{F}_p)| = p + 1 - a_p$.

Key Theoretical Insights

The research provides a significant advancement in characterizing these mathematical objects through several key contributions:

1. Generalization to $m$ Prime Factors

While previous studies often focused on the simplest case where $n$ is the product of two primes ($n=pq$), this paper extends the analysis to squarefree numbers with an arbitrary number of prime factors ($n = p_1 p_2 \dots p_m$). Theorem 2.5 establishes that such numbers are either relatively small or are composed of primes with specific trace values, primarily $a_p = 1$ or $a_p = -1$.

2. Correcting the Bounding Error

The authors identified and corrected a bounding error in earlier literature regarding the relationship between factors $p$ and $q$ in the $n=pq$ case. They proved that if $n=pq$ is a Type I number and $p$ falls within a specific range relative to $q$ (specifically $13 \le p \le \sqrt{q}/16$), then both $p$ and $q$ must be anomalous. This refinement provides a much stricter and more accurate "too small" condition than previously suggested.

3. The Probabilistic Limit

One of the paper's most striking results is Theorem 3.7. Using a combination of Hasse’s Theorem and the Chinese Remainder Theorem, the authors perform a probabilistic analysis of randomly chosen elliptic curves. They prove that as the prime factors $p$ and $q$ grow toward infinity, the probability that a Type I elliptic Korselt number $n=pq$ is a product of two anomalous primes approaches 100% (1.0). This effectively means that for large $n$, the "imposter" behavior is almost exclusively driven by the presence of anomalous primes.

Computational Verification

To support their theoretical conjectures, the authors conducted extensive numerical simulations. They developed an algorithmic trial system that randomly selected primes $p, q$ up to a bound $N$ and tested various elliptic curves for the Korselt condition.

The empirical data strongly mirrored the theoretical predictions. As the bound $N$ increased from 64 to 65,536, the observed probability $\text{Pr}(N)$ that the factors were anomalous rose from 0.614 to 0.995. This near-unity result provides robust evidence for the asymptotic behavior described in Theorem 3.7.

Implications and Future Directions

The paper also touches upon the infinitude of these numbers. By invoking the Hardy-Littlewood Conjecture, the authors argue that there are infinitely many such elliptic pseudoprimes for certain classes of elliptic curves (such as those in the form $y^2 = x^3 + D$).

However, some limitations remain. The strongest probabilistic results are currently confined to the $n=pq$ case. While the authors have laid the groundwork for $m$ factors, a full probabilistic characterization for $m > 2$ remains an open area for future research. Additionally, the reliance on the unproven Hardy-Littlewood Conjecture for the infinitude argument highlights a common boundary in modern number theory.

Conclusion

"Anomalous Primes and the Elliptic Korselt Criterion" successfully bridges the gap between elliptic curve group structures and classical primality theory. By identifying anomalous primes as the essential components of Type I elliptic Korselt numbers, the authors have provided a clearer map of the landscape of elliptic pseudoprimes, correcting previous errors and setting the stage for further exploration into higher-order composite numbers.

Summary updated

BibTeX
@article{babinkostova2019anomalous,
  author = {Liljana Babinkostova and Jackson Bahr and Y.H. Kim and Eric Neyman and Graham K. Taylor},
  title = {{Anomalous primes and the elliptic Korselt criterion}},
  journal = {Journal of Number Theory},
  year = {2019},
  doi = {10.1016/j.jnt.2019.02.013},
}
Figure