🔢 mathematics

Unconditional Primality Certificates for the Hexagonal 3-smooth Family p = 3m(m+1) + 1: Deterministic Pocklington Witnesses and Arithmetic Filters

This paper establishes a deterministic primality certification method for the hexagonal 3-smooth family $p = 3m(m+1) + 1$ by deriving exact congruence conditions that guarantee the validity of witnesses $w_2=5$ and $w_3=7$ via quadratic and cubic reciprocity, respectively, while employing efficient arithmetic filters to rapidly eliminate non-prime candidates.

Original authors: Hassane Bakkaoui

Published 2026-06-18

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Hassane Bakkaoui

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to prove that a massive number is truly "prime" (meaning it can only be divided by 1 and itself). In the world of big numbers, this is like trying to prove a giant, complex lock has no hidden keys other than the master key. Usually, this proof is a guessing game where you try different keys until one fits, hoping you got lucky.

This paper, by Hassane Bakkaoui, introduces a new, highly organized way to solve this puzzle for a specific family of numbers. Here is the breakdown using everyday analogies:

1. The Special Lock (The Number Family)

The paper focuses on a specific type of number lock defined by the formula $p = 3m(m + 1) + 1$ .

The Analogy: Think of these numbers as a special line of safes. The author discovered that if you build these safes using a specific recipe (where the variable $m$ is made only of the "building blocks" 2 and 3), the internal mechanism of the safe is unusually simple.
The Breakthrough: Because of this specific recipe, the author knows exactly how the safe is constructed before even trying to open it. This allows them to skip the usual "guessing game" and use a shortcut method (called the Pocklington–Lehmer criterion) that guarantees a proof of primality.

2. The Two Master Keys (The Witnesses)

To prove a number is prime using this shortcut, you need to show two specific "witnesses" (or keys) that behave in a very specific way.

The Old Way: Previously, mathematicians just tried using the keys labeled "5" and "7" and hoped they worked. It was like saying, "I bet these two keys will always open this type of safe."
The New Discovery: The paper proves that 5 and 7 do not always work. Sometimes they are the wrong keys.
- The Rule for Key #5: This key only works if the "recipe numbers" used to build the safe follow a specific pattern (related to the numbers 1 and 2 when divided by 4).
- The Rule for Key #7: This key only works if the recipe avoids a specific pattern (related to the number 2 when divided by 7).
The Result: Instead of guessing, the author created a deterministic rulebook. You can now look at the recipe numbers, check a simple math chart, and know exactly which keys to use. If 5 and 7 don't fit the rule, the paper tells you exactly what to use instead. This turns a game of chance into a guaranteed, step-by-step procedure.

3. The Security Filters (Weeding out the fakes)

Before trying to open the safe with the master keys, the author set up three simple "security checkpoints" to filter out the numbers that are obviously not prime.

The Analogy: Imagine you have a warehouse full of 1,000 safes. You don't want to waste time trying to open the 870 that are obviously broken or fake.
The Filters:
1. The Mod-6 Check: A quick check to see if the number is even or divisible by 3.
2. The Mod-7 Check: A specific test that instantly rejects one-third of the candidates.
3. The "Square Root" Check: A test that eliminates numbers divisible by certain other primes.
The Efficiency: These three simple checks remove about 87% of all candidates immediately. It's like having a bouncer at a club who kicks out almost everyone before they even get to the door, saving a massive amount of time.

4. The Proof of Concept (The Big Win)

To show this system works, the author ran a computer program on a standard laptop (consumer hardware, not a supercomputer).

The Achievement: They successfully generated four unbreakable proofs of primality.
The Highlight: The largest number they proved was 29,998 digits long. To visualize this, if you wrote that number out, it would fill a small book.
The Verification: They didn't just trust their own computer; they re-verified the result on a different system to ensure the "keys" (5 and 7) worked perfectly according to their new rules.

Summary

In short, this paper doesn't just find a new record-breaking prime number; it fixes the toolkit used to find them.

It identifies a specific family of numbers where the proof is easy.
It replaces "hopeful guessing" with exact rules for which keys (witnesses) to use.
It adds filters that discard 87% of bad numbers instantly.
It proves this entire system works on a regular laptop, creating a reliable, step-by-step factory for generating mathematical proof certificates.

The author is clear: this isn't about breaking new records for the sake of fame, but about creating a reliable, error-free method for a specific type of mathematical problem.

Technical Summary: Unconditional Primal Certificates for the Hexagonal 3-Smooth Family

Problem Statement
The paper addresses the problem of unconditional primality certification for a specific parametric subfamily of centered hexagonal numbers defined by $p = 3m(m + 1) + 1$ , where $m = 2^a 3^b - 1$ for integers $a, b \ge 1$ . While the Pocklington–Lehmer criterion offers a practical route to proving primality for generic large integers by exhibiting a fully factored divisor $F > \sqrt{p}$ of $p-1$ , the challenge lies in finding suitable "witnesses" (bases $w_q$ ) for each prime factor $q$ of $F$ . For this specific family, the divisor $F = 2^a 3^{b+1}$ is fully factored and satisfies $F > \sqrt{p}$ unconditionally. However, the validity of fixed witnesses (specifically $w_2=5$ and $w_3=7$ ) had previously been observed heuristically but lacked a rigorous, deterministic characterization. The paper seeks to resolve whether these fixed witnesses are universal and, if not, to provide exact conditions for their validity.

Methodology
The authors employ a combination of algebraic number theory and elementary arithmetic sieving:

Pocklington–Lehmer Framework: The proof relies on the criterion that $p$ is prime if there exist witnesses $w_2, w_3$ such that $w_q^{(p-1)/q} \not\equiv 1 \pmod p$ and $\gcd(w_q^{(p-1)/q}-1, p) = 1$ . Since $p \equiv 1 \pmod 6$ , this reduces to checking if $w_2$ is a quadratic non-residue and $w_3$ is a cubic non-residue modulo $p$ .
Quadratic Reciprocity: The validity of $w_2 = 5$ is analyzed using the Legendre symbol $\left(\frac{5}{p}\right)$ , relating it to the parameters $a$ and $b$ via properties of $m = 2^a 3^b - 1$ .
Cubic Reciprocity in Eisenstein Integers: The validity of $w_3 = 7$ is analyzed using the cubic residue symbol in $\mathbb{Z}[\omega]$ (where $\omega = e^{2\pi i/3}$ ). The authors utilize the explicit factorization $p = (m+1)^3 - m^3 = \pi \bar{\pi}$ to apply Eisenstein's law of cubic reciprocity. This allows the reduction of the cubic residuosity of 7 modulo $p$ to a condition on $m$ modulo 7.
Arithmetic Filters: Three elementary filters are derived to eliminate non-prime candidates before expensive large-number arithmetic:
- A modulo 6 identity (automatic).
- A $(-3)$ quadratic-residue sieve (eliminating primes $q \equiv 2 \pmod 3$ ).
- A modulo 7 forbidden-class test based on the residue classes of $(a \pmod 3, b \pmod 6)$ .

Key Contributions
The paper provides two rigorous theorems that replace heuristic assumptions with deterministic rules:

Theorem 4.1 (Witness $w_2=5$ ): The base 5 is a valid Pocklington witness if and only if $a - b \equiv 1, 2 \pmod 4$ . If this condition fails, 5 is a quadratic residue, and a different witness must be selected.
Theorem 4.5 (Witness $w_3=7$ ): The base 7 is a valid Pocklington witness if and only if $m \not\equiv 2 \pmod 7$ . This condition is equivalent to $(a \pmod 3, b \pmod 6) \notin \{(0, 1), (1, 5), (2, 3)\}$ .
Deterministic Selection Rule: Corollary 4.9 synthesizes these results into a complete algorithm for selecting witnesses. If the fixed witnesses fail the congruence checks, the algorithm deterministically selects the least quadratic or cubic non-residue, ensuring the certification process is provably correct rather than reliant on chance.
Generalization: Proposition 4.7 extends the analysis of the cubic character of 7 to the broader family $p = 3m^2 + 3m + 1$ (without the 3-smooth constraint), characterizing the cubic residuosity based on $m \pmod{21}$ .

Results

Filter Efficiency: The combination of the modulo 7 filter and the $(-3)$ sieve eliminates approximately 87% of candidate pairs $(a, b)$ before any large-number arithmetic (Miller–Rabin or Pocklington verification) is performed.
Computational Demonstration: A multi-core implementation ("PrimeQuest") generated four unconditional primality certificates on consumer hardware. The largest certificate corresponds to a prime of 29,998 decimal digits ( $m = 2^{19435}3^{19173} - 1$ ).
Verification: The 29,998-digit prime was independently re-verified. The certificate satisfies the Pocklington conditions with $w_2=5$ and $w_3=7$ , and the margin $2 \log_2 F - \log_2 p \approx 1.58$ bits confirms the unconditional primality.

Significance and Scope
The paper explicitly frames its contribution as structural and explicit rather than record-breaking.

Resolution of Heuristics: It resolves the open question of whether "5 and 7 always work" for this family, proving they do not, and replaces this uncertainty with exact congruence conditions.
Modest Claims: The authors state the paper "resolves no classical open problem." The 29,998-digit prime is not a record by general standards (as general-purpose ECPP handles much larger numbers), but serves as a demonstration of the framework's efficiency on commodity hardware.
Epistemic Status: All theoretical claims (Theorems 4.1, 4.5, 4.7 and the filters) are rigorous and unconditional. The computational results are verified by exact arithmetic. The work is presented as a follow-up to previous analytic theory, isolating a specific 3-smooth subfamily where the Pocklington method becomes fully deterministic and minimal.