Primality certificate

In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or unreliable primality test. "Succinct" usually means that the proof should be at most polynomially larger than the number of digits in the number itself (for example, if the number has b bits, the proof might contain roughly b² bits).

Primality certificates lead directly to proofs that problems such as primality testing and the complement of integer factorization lie in NP, the class of problems verifiable in polynomial time given a solution. These problems already trivially lie in co-NP. This was the first strong evidence that these problems are not NP-complete, since if they were, it would imply that NP is subset of co-NP, a result widely believed to be false; in fact, this was the first demonstration of a problem in NP intersect co-NP not known, at the time, to be in P.

Producing certificates for the complement problem, to establish that a number is composite, is straightforward: it suffices to give a nontrivial divisor. Standard probabilistic primality tests such as the Baillie–PSW primality test, the Fermat primality test, and the Miller–Rabin primality test also produce compositeness certificates in the event where the input is composite, but do not produce certificates for prime inputs.

Pratt certificates

The concept of primality certificates was historically introduced by the Pratt certificate, conceived in 1975 by Vaughan Pratt, ^[1] who described its structure and proved it to have polynomial size and to be verifiable in polynomial time. It is based on the Lucas primality test, which is essentially the converse of Fermat's little theorem with an added condition to make it true:

Lucas' theorem: Suppose we have an integer a such that:

• a^{n − 1} ≡ 1 (mod n),
• for every prime factor q of n − 1, it is not the case that a^{(n − 1)/q} ≡ 1 (mod n).

Then n is prime.

Given such an a (called a witness) and the prime factorization of n − 1, it's simple to verify the above conditions quickly: we only need to do a linear number of modular exponentiations, since every integer has fewer prime factors than bits, and each of these can be done by exponentiation by squaring in O(log n) multiplications (see big-O notation). Even with grade-school integer multiplication, this is only O((log n)⁴) time; using the multiplication algorithm with best-known asymptotic running time, due to David Harvey and Joris van der Hoeven, we can lower this to O((log n)³(log log n)) time, or using soft-O notation Õ((log n)³).

However, it is possible to trick a verifier into accepting a composite number by giving it a "prime factorization" of n − 1 that includes composite numbers. For example, suppose we claim that n = 85 is prime, supplying a = 4 and n − 1 = 6 × 14 as the "prime factorization". Then (using q = 6 and q = 14):

• 4 is coprime to 85,
• 4⁸⁵⁻¹ ≡ 1 (mod 85),
• 4^(85−1)/6 ≡ 16 (mod 85), 4^(85−1)/14 ≡ 16 (mod 85).

We would falsely conclude that 85 is prime. We don't want to just force the verifier to factor the number, so a better way to avoid this issue is to give primality certificates for each of the prime factors of n − 1 as well, which are just smaller instances of the original problem. We continue recursively in this manner until we reach a number known to be prime, such as 2. We end up with a tree of prime numbers, each associated with a witness a. For example, here is a complete Pratt certificate for the number 229:

• 229 (a = 6, 229 − 1 = 2² × 3 × 19),
  • 2 (known prime),
  • 3 (a = 2, 3 − 1 = 2),
    • 2 (known prime),
  • 19 (a = 2, 19 − 1 = 2 × 3²),
    • 2 (known prime),
    • 3 (a = 2, 3 − 1 = 2),
      • 2 (known prime).

This proof tree can be shown to contain at most ${\displaystyle 4\log _{2}n-4}$ values other than 2 by a simple inductive proof (based on theorem 2 of Pratt). The result holds for 3; in general, take p > 3 and let its children in the tree be p₁, ..., p_k. By the inductive hypothesis, the tree rooted at p_i contains at most ${\displaystyle 4\log _{2}p_{i}-4}$ values, so the entire tree contains at most

${\displaystyle 1+\sum _{i=1}^{k}(4\log _{2}p_{i}-4)=-4k+4\log _{2}p_{1}\cdots p_{k}\leq 4\log _{2}p-4,}$

since k ≥ 2, and p₁...p_k = p − 1. Since each value has at most log n bits, this also demonstrates that the certificate has a size of O((log n)²) bits.

Since there are O(log n) values other than 2, and each requires at most one exponentiation to verify (and exponentiations dominate the running time), the total time is O((log n)³(log log n)(log log log n)), or Õ((log n)³), which is quite feasible for numbers in the range that computational number theorists usually work with.

However, while useful in theory and easy to verify, actually generating a Pratt certificate for n requires factoring n − 1 and other potentially large numbers. This is simple for some special numbers such as Fermat primes, but currently much more difficult than simple primality testing for large primes of general form.

Atkin–Goldwasser–Kilian–Morain certificates

To address the problem of efficient certificate generation for larger numbers, in 1986 Shafi Goldwasser and Joe Kilian described a new type of certificate based on the theory of elliptic curves. ^[2] This was in turn used by A. O. L. Atkin and François Morain as the basis for Atkin-Goldwasser-Kilian-Morain certificates, which are the type of certificates generated and verified by elliptic curve primality proving (ECPP) systems. ^[3] Just as Pratt certificates are based on Lucas's theorem, Atkin–Goldwasser–Kilian–Morain certificates are based on the following theorem of Goldwasser and Kilian (lemma 2 of "Almost All Primes Can Be Quickly Certified"):

Theorem: Suppose we are given:

• a positive integer n not divisible by 2 or 3;
• M_x, M_y, A, B in ${\displaystyle \mathbb {Z} _{n}}$ (the integers mod n) satisfying M_y² = M_x³ + AM_x + B and with 4A³ + 27B² coprime to n;
• a prime ${\displaystyle q>n^{1/2}+1+2n^{1/4}}$.

Then M = (M_x, M_y) is a non-identity point on the elliptic curve y² = x³ + Ax + B. Let kM be M added to itself k times using standard elliptic-curve addition. Then, if qM is the identity element I, then n is prime.

Technically, an elliptic curve can only be constructed over a field, and ${\displaystyle \mathbb {Z} _{n}}$ is only a field if n is prime, so we seem to be assuming the result we're trying to prove. The difficulty arises in the elliptic-curve addition algorithm, which takes inverses in the field that may not exist in ${\displaystyle \mathbb {Z} _{n}}$. However, it can be shown (lemma 1 of "Almost All Primes Can Be Quickly Certified") that if we merely perform computations as though the curve were well-defined and do not at any point attempt to invert an element with no inverse, the result is still valid; if we do encounter an element with no inverse, this establishes that n is composite.

To derive a certificate from this theorem, we first encode M_x, M_y, A, B, and q, then recursively encode the proof of primality for q < n, continuing until we reach a known prime. This certificate has size O((log n)²) and can be verified in O((log n)⁴) time. Moreover, the algorithm that generates these certificates can be shown to be expected polynomial time for all but a small fraction of primes, and this fraction exponentially decreases with the size of the primes. Consequently, it's well-suited to generating certified large random primes, an application that is important in cryptography applications such as generating provably valid RSA keys.

Pocklington-based certificates

Provable prime generation based on variants of Pocklington's theorem (see Pocklington primality test) ^[4] can be efficient techniques for generating primes (cost is generally less than probabilistic generation) with the added benefit of built in primality certificates. While these may seem to be special primes, notice that every prime integer could be generated with a Pocklington based provable generation algorithm.

Pocklington primality tests

Let ${\displaystyle P=Rh+1}$ where ${\displaystyle R=\prod q_{j}^{e_{j}}}$ where ${\displaystyle q_{j}}$ are distinct primes with ${\displaystyle e_{j}}$ an integer greater than zero and a witness ${\displaystyle g}$ such that:

1. ${\displaystyle g^{Rh}\equiv 1{\bmod {P}}}$

1

2. ${\displaystyle \gcd((g^{Rh/q_{j}}-1{\bmod {P}}),P)=1}$ for all ${\displaystyle q_{j}}$.

2

Then P is prime if one of the following holds:

a) (see [5] ) ${\displaystyle R\geq h}$ or equivalently ${\displaystyle R>P^{1/2}}$

a

b) (see [6] : Corollary 1 ) ${\displaystyle R\geq h^{1/2}}$ or equivalently ${\displaystyle R>P^{1/3}}$ and with ${\displaystyle {\begin{array}{lr}a\equiv h{\bmod {R}}&0\leq a<R\\b=(h-a)/R\end{array}}}$, such that ${\displaystyle (a-4b)\neq 0}$ and there exists a small prime ${\displaystyle r>2}$ such that ${\displaystyle (a-4b)^{r/2}\neq 1{\bmod {r}}}$.

b

Pocklington primality certificate

A Pocklington primality certificate consists of the prime P, a set primes ${\displaystyle q_{j}}$ dividing ${\displaystyle (P-1)}$, each with their own Pocklington prime certificate or small enough to be a known prime, and a witness ${\displaystyle g}$.

The bits needed for this certificate (and order of computational cost) should range from approximately ${\displaystyle \log _{2}{P}\left(1+\sum _{k=1}^{\infty }{\frac {1}{3^{k}}}\right)=1.5\log _{2}{P}}$ for version ( b ) to ${\displaystyle \log _{2}{P}\left(1+\sum _{k=1}^{\infty }{\frac {1}{2^{k}}}\right)=2\log _{2}{P}}$ for version ( a )

A small example

Let ${\displaystyle P=1056893}$. Note that ${\displaystyle (P-1)=1621\cdot 163\cdot 2^{2}}$ and ${\displaystyle P^{1/2}=1028.053\ldots }$, ${\displaystyle P^{1/3}=101.86156\ldots }$.

• Using the 'witness' 2, equation 1 is satisfied and 2 using ${\displaystyle q=163}$ and ${\displaystyle q=1621}$.
• For version a , the certificate needs only ${\displaystyle P=1056893,\ q=1621,\ g=2}$.
• for version b , the certificate needs only ${\displaystyle P=1056893,\ q=163,\ g=2}$, but there's a bit more work to do:
  • ${\displaystyle h=(1056893-1)/163=6484}$
  • ${\displaystyle a\equiv h\equiv 127{\bmod {163}}}$ and ${\displaystyle b=\left(6484-127\right)/163=39}$
  • Using ${\displaystyle r=3}$ fails: ${\displaystyle \left(127^{2}-4\cdot 39\right)^{(3-1)/2}\equiv (1^{2}-0)^{1}\equiv 1{\bmod {3}}}$
  • Using ${\displaystyle r=5}$ succeeds: ${\displaystyle \left(127^{2}-4\cdot 39\right)^{(5-1)/2}\equiv (2^{2}-1)^{2}\equiv 2{\bmod {5}}}$, and ${\displaystyle P}$ is prime.

Gerbicz-based certificate

Gerbicz-based certificate seek to prove the correctness of a modular exponentiation process as used in the Proth and Fermat probabilistic tests. One form has been adapted to the deterministic Lucas–Lehmer–Riesel test. This type of certificate take ${\displaystyle O(\log n)}$ space as well as time to produce. The produced certificate takes ${\displaystyle O(\log \log n)}$ space to transmit and ${\displaystyle O(1)}$ squarings to verify. It is applied to very large numbers.

Gerbicz-Pietrzak scheme

Great Internet Mersenne Prime Search and allied projects such as (part of) PrimeGrid use Pavel Atnashev's "Gerbicz-Pietrzak" scheme, which combines Gerbicz's error checking for modular exponentiation with Pietrzak's verifiable delay function for producing an easily verifiable "proof" of a modular exponentiation to a power of 2^m. ^{[7] [8]}

The Gerbicz error-checking scheme was originally defined for the Proth test, but was later extended to the Fermat primality test. The original form verifies the computation ${\displaystyle u(t)={a^{k}}^{2^{t}}{\pmod {N}}}$ by adding an additional variable ${\displaystyle d(t)=\textstyle \prod _{i=0}^{t}u(iL){\pmod {N}}}$ and an arbitrary scaling constant L. There is therefore a recurrence relation of ${\displaystyle d(t+1)=d(t)\cdot u((t+1)\cdot L){\pmod {N}}}$ which can be used to update d(t) every L iterations of exponential doubling. There is also a relation ${\displaystyle d(t+1)=u(0)\cdot d(t)^{2^{L}}{\pmod {N}}}$, which is used to check the computation every L² iterations. A mismatch would result in a rollback to a previously saved "checkpoint" tuple of ${\displaystyle (t,u,d)}$. ^[9]

With the addition of the Pietrzak VDF scheme, ^[10] the calculating client generates a "certificate" file using the saved "checkpoint" residues from the computation, resulting in a file of ${\displaystyle O(\log(m/L))}$ elements. It uploads the certificate to a server, which then assigns it to a "verifier" client. The verifier then uses the non-interactive version of the Pietrzak scheme to check the result. ^[11]

Gerbicz-Li scheme

The main limitation of Gerbicz-Pietrzak is that it only applies to modular exponentiation to a power of 2^m. The Gerbicz-Li scheme was developed for PrimeGrid to overcome the limitation, verifying left-to-right modular exponentiation to any power n. Let L be the length of the binary expansion of n, so that ${\displaystyle n=n_{0}2^{0}+n_{1}2^{1}+\dots +n_{L-1}2^{L-1}}$. The process to be verified is to calculate ${\displaystyle u_{i}=a^{\lfloor n/2^{i}\rfloor }}$ by the following recurrence relation:

$${\displaystyle {\begin{aligned}u_{i}={\begin{cases}1&L\leq i\\u_{i+1}^{2}\cdot a^{n_{i}}&{\text{otherwise}}\end{cases}}\end{aligned}}}$$

There is therefore a relation ${\displaystyle u_{i}=u_{i+j}^{2^{j}}a^{\left\lfloor {\frac {n}{2^{i}}}\right\rfloor {\bmod {2}}^{j}}}$. As with the Gerbicz scheme, the calculating client saves ${\displaystyle u_{0},u_{B},u_{2B},\dots }$ for some constant ${\displaystyle B}$ which is a multiple of ${\displaystyle L}$. It then checks the equivalences between ${\displaystyle u_{iB}}$ and ${\displaystyle u_{(i+1)B}}$ every ${\displaystyle B}$ blocks, adding a random weight term ${\displaystyle w_{i}}$ for soundness in the proof for security:

$${\displaystyle {\begin{aligned}\prod _{i=0}u_{iB}^{w_{i}}&{\overset {\text{?}}{=}}\prod _{i=0}u_{(i+1)B}^{w_{i}2^{B}}a^{\left(\left\lfloor {\frac {n}{2^{iB}}}\right\rfloor {\bmod {2}}^{B}\right)w_{i}}\\&=\left(\prod _{i=0}u_{(i+1)B}^{w_{i}}\right)^{2^{B}}a^{\sum \limits _{i=0}\left(\left\lfloor {\frac {n}{2^{iB}}}\right\rfloor {\bmod {2}}^{B}\right)w_{i}}\end{aligned}}}$$

Hashing is similarly used to produce a non-interactive proof for use by PrimeGrid operators. ^[11]

Pavel Atnashev has further generalized Gerbicz-Li to the computation of Lucas sequences terms with ${\displaystyle Q=-1}$. ^[12] This generalization is used in his "Morrison test", a generalization of the LLR test with Rödseth starting value, in the PrimeGrid software "PRST". ^[13]

AKS certificate ("PRIMES is in P")

"PRIMES is in P" ^[14] was a breakthrough in theoretical computer science. This article, published by Manindra Agrawal, Nitin Saxena, and Neeraj Kayal in August 2002, proves that the famous problem of checking primality of a number can be solved deterministically in polynomial time. The authors received the 2006 Gödel Prize and 2006 Fulkerson Prize for this work.

Because primality testing can now be done deterministically in polynomial time using the AKS primality test, a prime number could itself be considered a certificate of its own primality. This test runs in Õ((log n)⁶) time. In practice this method of verification is more expensive than the verification of Pratt certificates, but does not require any computation to determine the certificate itself.

Cutoff for "known primes"

From exhaustive trials, it is known that the Baillie–PSW primality test has no pseudoprimes below 2⁶⁴. As a result 2⁶⁴ is a cutoff after which prime certificates are expected of provided numbers. ^[15]

References

1. Vaughan Pratt. "Every prime has a succinct certificate". SIAM Journal on Computing, vol. 4, pp. 214–220. 1975. Citations, Full-text.
2. Goldwasser, S. and Kilian, J. "Almost All Primes Can Be Quickly Certified". Proc. 18th STOC. pp. 316–329, 1986. Full text.
3. Atkin, A O.L.; Morain, F. (1993). "Elliptic curves and primality proving" (PDF). Mathematics of Computation . 61 (203): 29–68. Bibcode:1993MaCom..61...29A. doi: 10.1090/s0025-5718-1993-1199989-x . JSTOR   2152935. MR   1199989.
4. Pocklington, Henry C. (1914–1916). "The determination of the prime or composite nature of large numbers by Fermat's theorem". Proceedings of the Cambridge Philosophical Society. 18: 29–30.
5. Crandall, Richard; Pomerance, Carl. "Prime Numbers: A computational perspective" (2 ed.). Springer-Verlag, 175 Fifth Ave, New York, New York 10010, U.S.A., 2005.
6. Brillhart, John; Lehmer, D. H.; Selfridge, J. L. (April 1975). "New Primality Criteria and Factorizations of 2^m ± 1" (PDF). Mathematics of Computation. 29 (130): 620–647. doi: 10.1090/S0025-5718-1975-0384673-1 . JSTOR   2005583.
7. Woltman, George (2020-06-16). "The Next Big Development for GIMPS". GIMPS forum. Retrieved 20 May 2022.
8. "GIMPS - The Math - PrimeNet". www.mersenne.org.
9. Gerbicz, Robert (2017). "Fast and robust error checking on Proth/Pepin tests".
10. Boneh, Dan; Bünz, Benedikt; Fisch, Ben (2018). A Survey of Two Verifiable Delay Functions (Report). Retrieved 2025-10-06.
11. Darren Li; Yves Gallot (8 Feb 2023). "An Efficient Modular Exponentiation Proof Scheme". arXiv.
12. "prst/src/lucasmul.cpp at main · patnashev/prst". GitHub.
13. Atnashev, Pavel. "A simpler alternative to Lucas–Lehmer–Riesel primality test". Cryptology ePrint Archive.
14. Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (September 2004). "PRIMES is in P" (PDF). Annals of Mathematics . 160 (2): 781–793. doi: 10.4007/annals.2004.160.781 . JSTOR   3597229. MR   2123939.
15. Nicely, Thomas R. (2012-01-13) [First published 2005-06-10]. "The Baillie–PSW Primality Test". trnicely.net. Archived from the original on 2019-11-21. Retrieved 2013-03-17.

External links

• Mathworld: Primality Certificate
• Mathworld: Pratt Certificate
• Mathworld: Atkin-Goldwasser-Kilian-Morain Certificate
• The Prime Glossary: Certificate of Primality
• Vašek Chvátal. Lecture notes on Pratt's Primality Proofs. Department of Computer Science. Rutgers University. PDF version at Concordia University.