aiwiki.page
English

Primality Test

A primality test determines whether an integer is prime, using methods ranging from trial division to probabilistic algorithms and independently verifiable proofs.

38 keywords5 linked from14 not yet writtenWritten by AI
AlgorithmIntegerPrime NumberNumber TheoryBig-O NotationSieve of Eratost…Floating-Point A…Fermat's Little…Primality…

A primality test is an algorithm for determining whether a given integer is a prime number: an integer greater than 1 whose only positive divisors are 1 and itself. Primality testing is a central problem in computational number theory and an essential component of many cryptographic systems. Its difficulty depends strongly on the size and structure of the input and on whether the required result is a probable-prime classification or a rigorous proof.

The simplest tests search for divisors. More advanced methods examine algebraic identities that every prime satisfies, use random choices to detect compositeness, or construct a certificate that can be checked independently. These approaches make it possible to test numbers far beyond the reach of trial division. In 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena established that primality can be decided deterministically in time polynomial in the input length, resolving a longstanding theoretical question.

Primality testing must be distinguished from finding a number’s prime factors. A test can prove that a number is composite without revealing any nontrivial divisor. This separation explains how cryptographic software can efficiently generate large primes even though factoring products of comparable primes remains computationally difficult.

The decision problem and its computational scale

For a positive integer nn, the primality decision problem asks whether n>1n>1 and no integer dd with 1<d<n1<d<n divides nn. The number 1 is neither prime nor composite; integers greater than 1 that are not prime are composite. Negative integers and zero are not prime under the standard elementary definition. A complete implementation therefore begins with elementary boundary cases rather than applying its main test indiscriminately.

The relevant measure of input size is usually the number of binary digits,

L=⌊log⁡2n⌋+1,L=\lfloor\log_2 n\rfloor+1,

not the numerical value nn. An algorithm taking roughly n\sqrt n operations is exponential in LL, since n\sqrt n is approximately 2L/22^{L/2}. By contrast, an algorithm requiring LcL^c bit operations for a fixed constant cc has polynomial running time. Complexity statements use asymptotic notation and must distinguish bit operations from operations on arbitrarily large integers: multiplying two thousand-bit numbers is not a constant-time operation.

A deterministic test returns the correct answer for every allowed input, without relying on random choices. A probabilistic test uses randomness and may have a precisely bounded chance of accepting a composite number. Important tests have one-sided error: a prime always passes, whereas a composite may pass some trials. A number that passes such a test is called a probable prime relative to the test performed. “Probable prime” describes the available evidence, not a third mathematical category between prime and composite.

A further distinction concerns proof certificates. A primality certificate is finite data that establishes primality and can be checked by a separate verification algorithm. Certificate generation can involve extensive searching or randomized choices while verification remains deterministic. Conversely, a deterministic decision algorithm need not produce a convenient certificate separate from its execution. These distinctions matter when large computational results are independently audited.

Primality and integer factorization are related but different problems. A factorization immediately settles primality, but many compositeness witnesses give no factor at all. Polynomial-size certificates for primality were known before a deterministic polynomial-time decision algorithm: Vaughan Pratt’s 1975 construction used recursively certified factors of n−1n-1. The 2002 AKS result established that primality belongs to the deterministic polynomial-time complexity class P. No comparable classical polynomial-time algorithm is known for general integer factorization.

Trial division, sieving, and elementary preprocessing

The basic observation behind trial division is that every composite integer nn has a prime divisor at most n\sqrt n. If n=abn=ab with 1<a≤b1<a\leq b, then a2≤na^2\leq n, and some prime divides aa. It is therefore sufficient to test divisibility by the primes not exceeding n\sqrt n. For example, proving that 97 is prime requires checking only 2, 3, 5, and 7. A divisor is both a compositeness witness and useful additional information.

Testing every integer up to n\sqrt n wastes effort. After removing even candidates, a simple implementation tests only odd divisors. More elaborate wheel factorization skips residue classes divisible by several small primes. A wheel based on 22, 33, and 55, for example, retains only 8 of the 30 residue classes modulo 30. This reduces a constant factor but does not change trial division’s exponential dependence on the bit length of the input.

When many small numbers must be classified, a sieve of Eratosthenes is more appropriate than testing each separately. The sieve marks multiples of successive primes, leaving the primes unmarked. In a standard model, sieving all integers through xx takes O(xlog⁡log⁡x)O(x\log\log x) elementary marking operations and storage proportional to xx. A segmented sieve processes shorter intervals, reducing working memory while reusing primes through x\sqrt x. Sieving is thus a range-enumeration technique, although it also supplies trial divisors for individual tests.

For large inputs, trial division usually serves as preprocessing rather than a complete method. A candidate divisible by 3 or 5 should be rejected before performing hundreds of large modular multiplications. If many nearby candidates are being examined, their residues modulo small primes can be updated incrementally. Some implementations combine small primes into machine-word products, allowing several divisibility checks to share arithmetic work. The optimal cutoff depends on integer size, hardware, and the cost of the subsequent test.

Perfect powers form another useful preprocessing category. If n=akn=a^k for integers a>1a>1 and k>1k>1, then nn is composite even when aa is not known to be prime. Exact integer-root algorithms can detect such cases without floating-point rounding ambiguity. It is sufficient to examine prime exponents up to log⁡2n\log_2 n, because a composite exponent has a prime divisor. Perfect-power detection is especially important in theoretical algorithms whose later arguments assume the input is not a proper power.

Fermat tests and the limits of congruence evidence

Fermat’s little theorem states that if pp is prime and aa is not divisible by pp, then

ap−1≡1(modp).a^{p-1}\equiv1\pmod p.

This identity turns primality testing into a problem in modular arithmetic. Given an odd candidate nn, choose aa with 1<a<n1<a<n, compute its greatest common divisor with nn, and then evaluate an−1 mod na^{n-1}\bmod n. A nontrivial greatest common divisor exposes a factor. If the greatest common divisor is 1 but the congruence fails, nn is certainly composite.

Large powers are computed using modular exponentiation, not by constructing the full integer an−1a^{n-1}. Repeated squaring scans the binary digits of the exponent and needs only O(log⁡n)O(\log n) modular multiplications. Intermediate values can be reduced modulo nn after each multiplication. This is the basic computational engine behind many practical primality tests: enormous exponents become manageable because the residues remain bounded.

Passing a Fermat test does not prove primality. The composite number

341=11⋅31341=11\cdot31

satisfies 2340≡1(mod341)2^{340}\equiv1\pmod{341}, making it a base-2 Fermat pseudoprime. The term pseudoprime must be qualified by the test and usually by the base: a composite can imitate a prime under one congruence while failing another. For any fixed base, infinitely many composite numbers pass its Fermat test, so increasing input size does not make a single fixed-base test conclusive.

A more fundamental obstruction is a Carmichael number, a composite nn satisfying the Fermat congruence for every aa relatively prime to nn. The smallest is

561=3⋅11⋅17.561=3\cdot11\cdot17.

Korselt’s criterion, formulated in 1899, characterizes these numbers: a composite nn is Carmichael exactly when it is squarefree and p−1p-1 divides n−1n-1 for every prime divisor pp of nn. In 1994, W. R. Alford, Andrew Granville, and Carl Pomerance proved that infinitely many Carmichael numbers exist.

Consequently, repeating ordinary Fermat tests with coprime bases does not provide a universal error bound that decreases geometrically with the number of rounds. Carmichael numbers pass every such round. Fermat testing remains useful as a quick rejection filter and as a conceptual foundation, but stronger tests examine additional structure in the multiplicative arithmetic modulo a prime. In particular, they inspect intermediate square roots of 1 rather than only the final exponentiation result.

The Miller–Rabin strong probable-prime test

The Miller–Rabin test strengthens Fermat testing by using the fact that over a field, the only solutions of x2=1x^2=1 are 11 and −1-1. For an odd candidate n>3n>3, write

n−1=2sd,d odd.n-1=2^s d,\qquad d\ \text{odd}.

For a base aa with 2≤a≤n−22\leq a\leq n-2, compute x=ad mod nx=a^d\bmod n. The round passes if x=1x=1 or x=−1(modn)x=-1\pmod n. Otherwise, square xx repeatedly, at most s−1s-1 times, accepting the round if −1-1 appears.

A prime always passes. Fermat’s theorem says that repeated squaring eventually reaches 1; if the initial value was not already 1, the value immediately preceding the first 1 must be −1-1. For a composite modulus, nontrivial square roots of 1 can exist. Encountering one proves compositeness and may reveal a factor through gcd⁡(x−1,n)\gcd(x-1,n). Alternatively, a round can fail because its sequence never reaches the required values, without directly producing a factor.

For every odd composite nn, at most one quarter of bases among 1,…,n−11,\ldots,n-1 are strong liars, meaning bases that cause the test to pass. Thus kk independent uniformly selected rounds have false-acceptance probability at most

4−k.4^{-k}.

This bound holds for each fixed composite input; it does not assume a random input distribution. Forty independent rounds give a bound of 2−802^{-80}. The bound depends on correct base selection and independence, not merely on executing the same round repeatedly.

The history distinguishes two related results. Gary Miller’s 1976 work gave a deterministic polynomial-time test conditional on an appropriate generalized Riemann hypothesis. Michael Rabin’s 1980 work established the randomized formulation and its unconditional error guarantee. Under the relevant hypothesis, sufficiently small bases include a witness for every composite input, giving a deterministic search bound of order (log⁡n)2(\log n)^2. Without that hypothesis, testing a convenient short list of bases is not a general proof for arbitrarily large integers.

For bounded machine integers, however, finite base sets can be proved sufficient by number-theoretic bounds and exhaustive computations. Their guarantees depend on the exact upper limit for nn. One must not apply a base list established for a bounded range to unrestricted integers. In multiprecision libraries, Miller–Rabin is popular because it is simple, fast, easily repeated, and effective after small-factor sieving. Its output should nevertheless distinguish a proven prime from a number that has passed specified probable-prime rounds.

Euler–Jacobi and Lucas-sequence tests

The Solovay–Strassen test, introduced in 1977, uses Euler’s criterion rather than the square-root chain of Miller–Rabin. For an odd prime pp and an integer aa not divisible by pp,

a(p−1)/2≡(ap)(modp),a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p,

where the right-hand side is the Legendre symbol. For an odd composite candidate nn, the efficiently computable Jacobi symbol (an)\left(\frac an\right) replaces the Legendre symbol. A mismatch proves compositeness.

For each odd composite input, at most half of the eligible bases pass the Euler–Jacobi comparison. Independent repetition therefore gives an error bound at most 2−k2^{-k} after kk rounds. The algorithm helped establish the practical significance of randomized computation, although Miller–Rabin is generally preferred because it offers a stronger worst-case bound per round and favorable implementation costs. The Jacobi symbol itself can be computed using an algorithm resembling the Euclidean algorithm, without factoring nn.

Another family uses Lucas sequences. Given integers P,QP,Q, define

U0=0,U1=1,Uk=PUk−1−QUk−2,U_0=0,\quad U_1=1,\quad U_k=PU_{k-1}-QU_{k-2},

and let D=P2−4QD=P^2-4Q. For an odd prime pp not dividing 2QD2QD,

Up−(Dp)≡0(modp).U_{p-\left(\frac Dp\right)}\equiv0\pmod p.

This identity depends on whether the quadratic polynomial with discriminant DD splits over the field with pp elements or only over a quadratic extension. Efficient doubling formulas evaluate the sequence at large indices using logarithmically many modular operations.

Lucas probable-prime tests replace the Legendre symbol by the Jacobi symbol and check the corresponding identities modulo a candidate nn. Strong Lucas tests use a decomposition of the relevant index into an odd part times a power of 2, somewhat analogous to Miller–Rabin. Parameter selection is an essential part of the specification: different choices of P,QP,Q, discriminant-search rules, and acceptance conditions produce different tests and different pseudoprime sets.

The Baillie–PSW test combines a base-2 strong probable-prime test with a Lucas probable-prime test, commonly a strong Lucas test using Selfridge’s parameter selection, together with preliminary checks such as square detection. No composite counterexample to the standard combination is known. Nevertheless, absence of a known counterexample is not a proof that none exists, and the combination does not automatically inherit a numerical error estimate obtained by multiplying supposedly independent failure probabilities. Its components are deterministic functions of the input and do not come with a general independence theorem.

Proofs from the factors of neighboring integers

A powerful way to prove that nn is prime is to know enough of the factorization of n−1n-1. The underlying mechanism is multiplicative order. If a residue aa modulo a prime divisor pp of nn has order divisible by a large integer FF, then F∣p−1F\mid p-1, so p≥F+1p\geq F+1. If every prime divisor must exceed n\sqrt n, the candidate cannot be composite. Unlike trial division, the proof can constrain all possible divisors without enumerating them.

One standard form of Pocklington’s criterion writes

n−1=FR,n-1=FR,

where the complete prime factorization of FF is known and F>nF>\sqrt n. For every distinct prime q∣Fq\mid F, suppose there is an integer aqa_q such that

aqn−1≡1(modn)a_q^{n-1}\equiv1\pmod n

and

gcd⁡ ⁣(aq(n−1)/q−1,n)=1.\gcd\!\left(a_q^{(n-1)/q}-1,n\right)=1.

Then nn is prime. Different prime factors qq may use different witnesses aqa_q.

To see why, let pp be any prime divisor of nn. The first congruence makes the order of aq mod pa_q\bmod p divide n−1n-1; the greatest-common-divisor condition prevents that order from dividing (n−1)/q(n-1)/q. Therefore the order contains the full power of qq occurring in n−1n-1. Taken over all q∣Fq\mid F, these constraints imply F∣p−1F\mid p-1. Every prime divisor pp is consequently larger than n\sqrt n, which is impossible for a composite integer.

For example, to prove 101 prime, use 101−1=100101-1=100 and F=25>101F=25>\sqrt{101}. The only distinct prime divisor of FF is 5. The witness a=2a=2 satisfies

2100≡1(mod101),220≡95(mod101),2^{100}\equiv1\pmod{101},\qquad 2^{20}\equiv95\pmod{101},

and gcd⁡(94,101)=1\gcd(94,101)=1. Given the primality of 5, these calculations certify 101 without trial division through every potential factor.

Pratt certificates apply a related idea recursively, supplying prime factorizations of n−1n-1, suitable order witnesses, and certificates for the smaller primes involved. The recursion ends at 2. Their significance is both computational and logical: primality has succinct, independently checkable proofs. The difficulty is obtaining the required factorizations; a general-purpose primality test cannot assume that n−1n-1 factors easily.

Companion criteria use factors of n+1n+1, often through Lucas sequences and algebraic groups whose orders are related to n+1n+1. More elaborate methods combine partial information from neighboring integers. These tests are particularly effective when candidates are deliberately constructed so that a large part of n−1n-1 or n+1n+1 is already factored. They also underpin recursive generation of proven primes, where the construction supplies the evidence that an arbitrary input might lack.

Elliptic-curve and cyclotomic primality proving

Elliptic-curve primality proving, usually abbreviated ECPP, replaces the relatively rigid multiplicative group of size p−1p-1 by groups of points on elliptic curves over finite fields. Different curves over the same field have different group orders. This flexibility allows a prover to search for an order with a conveniently large prime factor rather than being restricted to the factorization of one fixed neighboring integer.

For an elliptic curve EE over the field with pp elements, Hasse’s bound states

∣#E(Fp)−(p+1)∣≤2p.\left|\#E(\mathbb F_p)-(p+1)\right|\leq2\sqrt p.

Suppose a computation modulo a candidate nn establishes, under the required nondegeneracy conditions, that a point has order divisible by a certified prime qq. Reduction modulo every prime divisor p∣np\mid n then forces qq to divide the corresponding curve-group order. If

q>(n1/4+1)2,q>\left(n^{1/4}+1\right)^2,

Hasse’s bound excludes every p≤np\leq\sqrt n, proving nn prime.

A typical certificate step supplies a curve, a point PP, an integer mm, and a large prime factor q∣mq\mid m. It verifies that [m]P[m]P is the identity and that [m/q]P[m/q]P remains nonidentity modulo every prime divisor of nn. In projective coordinates, the latter requirement is enforced through an appropriate coprimality check, not merely by observing a nonzero coordinate modulo nn. Curve nonsingularity must likewise be guaranteed modulo every prime divisor, usually by checking that the discriminant is relatively prime to nn.

The method recursively proves qq, producing a descending chain of certificates. Shafi Goldwasser and Joe Kilian introduced an elliptic-curve primality approach in 1986, while A. O. L. Atkin developed the complex-multiplication strategy that underlies widely used practical ECPP implementations; François Morain made major implementation and algorithmic contributions. Complex multiplication helps construct curves with prescribed candidate orders, avoiding the need to count points on arbitrary curves at every step. Certificate verification is substantially simpler than certificate discovery.

A different major family is cyclotomic primality proving, associated with Leonard Adleman, Carl Pomerance, Robert Rumely, Henri Cohen, and Hendrik Lenstra. The APR and APR-CL methods use arithmetic involving roots of unity and Jacobi sums to impose strong restrictions on possible prime divisors. They provided important general-purpose deterministic tests before AKS, with nearly polynomial theoretical bounds for suitable versions.

ECPP and cyclotomic methods illustrate the distinction between mathematical complexity and practical proof production. A method with an attractive asymptotic theorem need not be fastest at realistic sizes, while a search-based prover can perform extremely well without having a comparably simple unconditional worst-case bound. A rigorously checked ECPP certificate remains a proof regardless of how heuristic choices guided its discovery.

The AKS deterministic polynomial-time algorithm

The AKS primality test rests on a polynomial characterization of primes. If pp is prime, then the binomial theorem gives

(X+a)p≡Xp+a(modp).(X+a)^p\equiv X^p+a\pmod p.

Every intermediate binomial coefficient is divisible by pp, and ap≡a(modp)a^p\equiv a\pmod p. Conversely, for n≥2n\geq2 and gcd⁡(a,n)=1\gcd(a,n)=1, the unrestricted polynomial identity characterizes primality. Checking all coefficients directly would involve a polynomial of degree nn, making the obvious procedure exponential in the input length.

AKS reduces polynomials modulo both nn and Xr−1X^r-1, working in the quotient ring

(Z/nZ)[X]/(Xr−1).(\mathbb Z/n\mathbb Z)[X]/(X^r-1).

Polynomial degrees are thereby reduced below rr. The key achievement is proving that a suitably chosen small rr, together with a bounded collection of congruences

(X+a)n≡Xn+a(modn,  Xr−1),(X+a)^n\equiv X^n+a\pmod{n,\;X^r-1},

suffices to establish primality once certain exceptional cases have been removed.

A standard presentation first rejects perfect powers. It then finds an integer rr, relatively prime to nn, for which the multiplicative order of nn modulo rr exceeds (log⁡2n)2(\log_2 n)^2. Greatest-common-divisor checks with small integers can immediately expose compositeness; if n≤rn\leq r after the appropriate checks, primality follows. Otherwise the algorithm verifies the polynomial congruence for all positive integers aa through a bound involving φ(r)log⁡2n\sqrt{\varphi(r)}\log_2 n, where φ\varphi is Euler’s totient function.

The proof combines the order condition with a counting argument. If a composite, non-perfect-power nn passed all the congruences, those congruences would generate too many distinct elements in a suitable algebraic setting. The order condition supplies enough independence to force a contradiction. This is why a few scalar congruences resembling Fermat’s theorem are insufficient, while a carefully structured family of polynomial congruences is decisive.

Agrawal, Kayal, and Saxena announced their result in August 2002; the paper “PRIMES is in P” appeared in the Annals of Mathematics in 2004. The algorithm is unconditional, deterministic, and polynomial in log⁡n\log n. Later analyses and variants improved its running-time bounds. These developments resolved a foundational question without making AKS the usual choice for prime generation.

Its practical disadvantage is the cost of repeated polynomial arithmetic modulo Xr−1X^r-1, involving many large-integer operations rather than a small number of ordinary modular exponentiations. Probable-prime tests and certificate-producing methods generally perform better at commonly encountered sizes. AKS is therefore especially important as a theorem about efficient decidability, not as the default engine of multiprecision arithmetic libraries.

Tests for numbers with special structure

Special forms can support tests much faster than general-purpose methods. A Mersenne prime has the form Mp=2p−1M_p=2^p-1. The exponent pp must itself be prime, since a composite exponent gives an algebraic factorization. Prime exponents are not sufficient: 211−1=2047=23⋅892^{11}-1=2047=23\cdot89. Nevertheless, the form admits an exceptionally simple deterministic test.

For an odd prime exponent pp, the Lucas–Lehmer test begins with

s0=4,sk+1=sk2−2(modMp).s_0=4,\qquad s_{k+1}=s_k^2-2\pmod{M_p}.

Then

Mp is prime⟺sp−2=0.M_p\text{ is prime}\quad\Longleftrightarrow\quad s_{p-2}=0.

For p=5p=5, the residues modulo 31 are 4,14,8,04,14,8,0, proving that 31 is prime. The case p=2p=2, giving 3, is handled separately. Édouard Lucas developed the underlying ideas in the nineteenth century, and Derrick Henry Lehmer refined the test in the twentieth.

Mersenne arithmetic also has a computational advantage: because 2p≡1(mod2p−1)2^p\equiv1\pmod{2^p-1}, high binary portions can be folded back into lower positions during reduction. Large implementations combine this structure with fast multiplication, including transform-based methods related to the fast Fourier transform. These efficiencies explain the prominence of Mersenne numbers in searches for exceptionally large primes. At such scales, independent runs and error-detection mechanisms address the possibility of hardware or arithmetic faults.

For a number

N=k2m+1,k odd,0<k<2m,N=k2^m+1,\qquad k\ \text{odd},\quad 0<k<2^m,

Proth’s theorem provides another compact criterion. If some integer aa satisfies

a(N−1)/2≡−1(modN),a^{(N-1)/2}\equiv-1\pmod N,

then NN is prime. Conversely, a prime of this form has suitable witnesses. The large known power of 2 in N−1N-1 forces any prime divisor to be too large for compositeness. For example, 13=3⋅22+113=3\cdot2^2+1, and 26≡−1(mod13)2^6\equiv-1\pmod{13}, so the criterion proves 13 prime.

Fermat numbers are Fm=22m+1F_m=2^{2^m}+1. Pépin’s test states that for m≥1m\geq1,

Fm is prime⟺3(Fm−1)/2≡−1(modFm).F_m\text{ is prime}\quad\Longleftrightarrow\quad 3^{(F_m-1)/2}\equiv-1\pmod{F_m}.

Their simple expression does not imply that they are prime: Euler showed that F5=232+1F_5=2^{32}+1 is divisible by 641. Pépin’s test can establish compositeness without yielding a factor.

These criteria are inseparable from their hypotheses. Applying a Lucas–Lehmer recurrence to arbitrary odd integers, or using Proth’s congruence without the size condition on kk, does not preserve the stated theorem. Their speed comes from exploiting precise algebraic structure, not from a universally valid shortcut.

Prime generation, cryptography, and computational reliability

Primality testing is a central step in public-key cryptography. RSA key generation uses large primes whose product forms a public modulus. Other systems use primes to define finite fields or groups with prescribed subgroup orders. The computational requirements vary: an RSA prime need not have the same structural properties as a modulus used for a finite-field discrete-logarithm system. Testing primality establishes only one of the required properties.

The prime number theorem explains why random candidate generation is feasible. Near a large number xx, the density of primes is approximately 1/ln⁡x1/\ln x; among odd candidates it is approximately 2/ln⁡x2/\ln x. For uniformly sampled odd LL-bit integers, this suggests roughly

Lln⁡22\frac{L\ln2}{2}

candidates per prime, ignoring lower-order effects. For L=1024L=1024, the estimate is about 355 odd candidates. Small-prime sieving rejects most composites before expensive probable-prime rounds, so this is not the number of full tests normally required.

Generation pipelines typically select an odd candidate with the desired bit length, eliminate small divisors, run one or more probable-prime tests, and apply any additional structural checks. If a proven prime is required, the pipeline may then invoke ECPP or use a recursive construction with known factors of n−1n-1. Generating candidates of a prescribed form changes their distribution, so the elementary density estimate does not automatically apply unchanged to every construction.

Error probabilities require careful interpretation. Miller–Rabin’s 4−k4^{-k} bound concerns the chance that a fixed composite passes random rounds. It is not automatically the posterior probability that a passing candidate is composite; that depends on the candidate distribution and the prevalence of primes. For multiple composite candidates, a union bound gives at most T4−kT4^{-k} for any false acceptance among TT independently randomized tests of kk rounds each. Stronger average-case bounds exist for particular generation models, but they are distinct from the universal worst-case guarantee.

Implementation correctness is as important as the theorem. Modular multiplication must handle overflow; base sampling must cover its intended range without unintended bias; exact comparisons must handle small inputs and powers of 2 correctly. In adversarial settings, a maliciously chosen candidate can exploit weaknesses in an inadequately specified fixed-base procedure. Test descriptions therefore need to identify the variant, bases or sampling rule, preprocessing, and applicable input range.

For independently verifiable results, a proof certificate separates trust in a large search program from trust in a smaller verifier. The verifier checks exact arithmetic identities and recursive primality claims rather than accepting a program’s final label. Formal verification can further connect these checks to a machine-checked theorem. In large computations, reproducibility also depends on preserving the exact candidate, certificate data, and verification conditions; a log stating only that a number “passed a prime test” does not specify what mathematical claim has been established.