A Conjecture on Primality Testing

Last modified on May 6, 2024

We begin with a conjecture on primality testing, which I first shared on my personal GitHub early last month.

Conjecture 1. Let $n \in \mathbb{Z}_{\textup{odd}}^+$ such that $2^{n-1} \equiv 1 \pmod{n}$ . Then, the following polynomial congruence holds iff $n$ is prime:

$\begin{align*} (x^4 + x)^n - x^{4n} - x^n = 0 \quad \in (\mathbb{Z}/n\mathbb{Z})[x]/(x^8 - x^2 + 2) \end{align*}$

By the binomial theorem, it is easy to see that the polynomial congruence will hold for all prime $n$ . Additionally, I have confirmed that there is no composite $n \leq 2^{64}$ which satisfies the test. If the conjecture is true, then it represents a $\tilde{O}(\log^2 n)$ primality test.

I am currently writing a paper to explain the proposed primality test in detail. For now, I’ll give some hints: The univariate congruence in the conjecture is the same as the following bivariate congruence

$\begin{align*} (x + y)^n - x^n - y^n = 0 \quad \in (\mathbb{Z}/n\mathbb{Z})[x,y]/(x^2 - y^2 + 2, y^4 - x) \end{align*}$

Start by arranging a system of congruences for the polynomial generators of the quotient ring. Then, consider what the system’s solutions imply about power residues modulo composite $n$ . Particularly, consider how said solutions relate to the individual prime factors of $n$ .

PRIMES is in… Quadratic Time?

It is seemingly difficult to prove that this test is deterministic (supposing this is true), however, it is relatively easy to show that it’s extremely unlikely for any composite $n$ to pass. In computing terms, you can think of the underlying mechanism for this as a “hashing” of the power residues modulo the prime factors of $n$ — if a subset of the power residues modulo composite $n$ ‘s prime factors do not miraculously align, then $n$ has no chance to pass the test.

Again, no pseudoprimes for this test are known, and I have checked for all $n$ up to $2^{64}$ . If there are indeed any pseudoprimes, then I expect that they will be of the form $n = p \cdot (2p - 1)$ , where $p$ is prime. It would be nice if pseudoprimes take this form, as such composite $n$ can be easily factored without impacting the running time. I do hope we can be so fortunate!

A Bonus Conjecture

Conjecture 2. Let $n \in \mathbb{Z}_{\textup{odd}}^+$ such that $2^{n-1} \equiv 1 \pmod{n}$ . Suppose the following polynomial congruence holds:

$\begin{align*} (x^2 + x)^n - x^{2n} - x^n = 0 \quad \in (\mathbb{Z}/n\mathbb{Z})[x]/(x^5 - x + 2) \end{align*}$

Then, either $n$ is prime or $n = p \cdot (2p-1)$ .

This conjecture exhibits the same time complexity as the test given by Conjecture 1, which is $\tilde{O}(\log^2 n)$ , but this variation is faster in practice. It is premised upon the same underlying principles. In this case, I experimentally manipulated the polynomial terms in the hope that I could “compress” the previous test without sacrificing accuracy. Despite the seemingly lossy simplifications, it is plausible that this test is incredibly strong. The smallest composite $n$ for which this version of the polynomial congruence holds, is

$\begin{align*} n = 3010871247360795253 = 1226961949 \cdot 2453923897 = p \cdot (2p-1) \end{align*}$