Absolute Primality Calculator for 8 Algebraic Forms

How to use

Type N as a decimal number (you may paste thousands of digits) or as an expression using + - * / ^, parentheses, n! (factorial) and n# (primorial, the product of the primes ≤ n). Press Test or Enter, or pick one of the examples.

Reading N from a file. With Load file… you can read N from a plain-text (.txt) file on your computer; the file is read by your browser and is not uploaded anywhere. If the file contains only digits, they are joined into one number even if they are split over several lines (spaces, line breaks and a trailing backslash on each line are ignored). Otherwise the first non-empty line is read as an expression, such as 3*2^100001+1. A long number is not shown in the box; the box shows the file name and the number of digits instead.

Testing a list. If the file has two or more lines that are not all digits, each non-empty line is read as one number or expression (lines starting with // or ; are skipped). Press Test and the numbers are tested one after another, without asking before long computations; each result goes to the Session log, and Cancel stops the whole list. With Download session log you can keep the table of verdicts and times.

You do not need to say which form your number has: the calculator computes N and examines the factored part of N-1 and N+1 to decide which theorem applies. For example, (2^2923-1)^2-2 is recognised as a Carol number and 6*2^3911+1 as the Proth number 3*2^3912+1.

The eight algebraic forms covered are:

Verdicts. Every test ends with one of three answers:

PRIME — proven. The report names the theorem that was applied, the known factorization it used and every condition that was verified. The link "Why does this prove it is prime?" explains that theorem.

COMPOSITE. The report gives a witness: a small prime factor, an algebraic factor, or a base for which N fails a property that every prime of its form must have, together with the Res64 residue (see "Composite verdicts and Res64" below).

Not admissible. The number has none of the structures above, or the known factored part of N-1 and N+1 is too small. The message explains what is missing, and no computation is attempted.

Time. Before a long computation the calculator shows an estimate and asks for confirmation when it exceeds one minute, and you can stop a computation in progress at any moment with the Cancel button next to Test. As a rough guide on a laptop: a 10,000-digit base-2 number takes a few seconds; a 10,000-digit number in another base takes about half a minute (N-1) or a minute (N+1). Numbers of up to about 632,000 digits are accepted; near that limit a single test can take several hours. The work is done by your own computer: nothing is sent to the server.

Your computer. Speed depends mainly on the speed of a single processor core (a test uses one core, so more cores do not make it faster); memory hardly matters. The results are identical on any processor; only the time changes. A modern high-end processor can be two or three times faster than a modest or older one, and a phone is usually slower than a laptop. The estimate shown before a long test is measured on your own device. For long tests, check your power settings before starting: set sleep and hibernation to "never" while the test runs, turn off battery-saver mode, and keep the laptop plugged in; a computer that goes to sleep pauses the computation. On phones and tablets keep the screen on and the browser in the foreground, because the system may suspend a browser that runs in the background.

Browsers. The calculator needs JavaScript with two features: BigInt (integers of any size) and Web Workers (computing in the background without freezing the page). Every current browser engine has both since 2020: Chromium (Chrome, Edge, Brave, Opera, Vivaldi, Samsung Internet), Gecko (Firefox) and WebKit (Safari, and every browser on iPhone and iPad), on computers and phones (phones are slower). It does not work in Internet Explorer, in older browser versions, with JavaScript disabled, or in browsers that render pages on a remote server (such as Opera Mini in data-saving mode). The page checks this when it opens and shows a notice if your browser lacks either feature.

Already have a probable prime? If another tool told you that a number of one of these forms is a probable prime, you can obtain its proof here in about the same time a probable-prime test takes.

Why does this prove it is prime?

All the theorems below share one idea: when enough of the factorization of N-1 or N+1 is known, one modular computation restricts every prime factor p of N to the form p ≡ 1 or p ≡ ±1 modulo the known part F. If that restriction leaves no room for a prime factor up to √N (or, in the Brillhart-Lehmer-Selfridge case, for the only factorization still possible), N must be prime. There is no "probable" step: the computation that tests N is itself the proof.

Proth's theorem (1878)

Let p be a prime factor of N. The order of a modulo p divides N-1 = k*2^n but not (N-1)/2, so it is a multiple of 2^n. Since that order also divides p-1, 2^n divides p-1, hence p > 2^n > √N (because k < 2^n). The calculator chooses a with Jacobi symbol (a/N) = -1; if N were prime, Euler's criterion would force a^((N-1)/2) ≡ -1. So the test cannot fail for a prime, and when it fails N is composite.

Pépin's test (1877)

This is Proth's theorem with k = 1 and a = 3. Because F_m ≡ 1 (mod 4) and F_m ≡ 2 (mod 3), quadratic reciprocity gives (3/F_m) = -1, so for a prime Fermat number the congruence must hold: the condition is necessary as well as sufficient. A number 2^n+1 whose exponent n has an odd factor d > 1 is divisible by 2^(n/d)+1 and is declared composite at once.

Lucas-Lehmer test (Lucas 1878, Lehmer 1930)

One has s(i) = ω^(2^i) + ω^(-2^i) with ω = 2+√3. If s(p-2) ≡ 0, then ω has order exactly 2^p modulo every prime factor q of M, inside a multiplicative group with fewer than q^2 elements; hence q^2 > 2^p > M and q > √M. If the exponent is composite, say p = a*b, then 2^a-1 divides 2^p-1 and N is declared composite at once.

Lucas-Lehmer-Riesel test (Riesel 1969; starting value by Rödseth 1994)

This generalizes the Lucas-Lehmer test, with the Lucas sequence V of parameter P in place of the powers of 2+√3. Rödseth's criterion chooses P with Jacobi symbols ((P-2)/N) = +1 and ((P+2)/N) = -1; this choice works for every k, including multiples of 3, which needed special treatment in Riesel's original test.

Pocklington's theorem (1914)

Let p be a prime factor of N. For each q, the order of a modulo p divides N-1 but not (N-1)/q, so it contains the full power of q that divides N-1; it also divides p-1. Collecting all q gives F | p-1, so p > F ≥ √N. To find F the calculator divides N-1 by every prime below 200,000 and by the prime factors of the bases that appear in your expression, and then uses only the primes needed to reach the threshold.

The Brillhart-Lehmer-Selfridge refinement (1975)

Every prime factor of N is at least F+1, and three of them would give a product of at least (F+1)^3 > N. So a composite N must be (a*F+1)(b*F+1) with a, b ≥ 1, that is N = a*b*F^2 + (a+b)*F + 1. Since N ≤ F^3, both a*b and a+b are smaller than F, so they are exactly the digits c2 and c1 of N in base F, and c1^2 - 4*c2 = (a-b)^2 is a perfect square. Conversely, if c1^2 - 4*c2 = s^2, then N = (a*F+1)(b*F+1) with a = (c1+s)/2 and b = (c1-s)/2. This lets the calculator prove numbers whose N-1 is factored only up to one third of its digits.

Lucas N+1 test (Lehmer 1930; Morrison 1975)

This is the analogue of Pocklington's theorem in the quadratic field of discriminant D. For a prime factor p of N, the first index m with p | U(m) (the "rank of apparition") divides p+1 or p-1, and the conditions force it to be a multiple of F; hence p ≡ ±1 (mod F) and p ≥ F-1 > √N. With Q = 1 the rank of apparition always divides (p±1)/2, which is why (N+1)/4 is used for q = 2 (with (N+1)/2 the condition could never hold). The cube-root (Brillhart-Lehmer-Selfridge type) variant for N+1 is not included; such numbers are reported as not admissible.

Factorials and primorials

For n!±1 and n#±1 the number N∓1 is n! or n#, whose factorization is completely known, so Pocklington/BLS (for +1) or the Lucas N+1 test (for -1) applies. The condition for q = 2 needs a base that is a quadratic non-residue of N. For n!+1 with n ≥ 4 every prime ≤ n is a residue (N ≡ 1 modulo each of them and modulo 8), so the base is taken above n: for example 1481 for 1477!+1. For primorials hundreds of primes q are involved; the calculator computes all the powers a^((N-1)/q) (or, for n#-1, the corresponding Lucas terms) with a "power tree", and checks all the gcd conditions with a single gcd of their product, so the cost stays close to a few modular exponentiations.

Composite verdicts and Res64

A composite verdict is always backed by a witness: a small prime factor (trial division up to 200,000), an algebraic factor, a factor found by a gcd, a perfect square, the Brillhart-Lehmer-Selfridge square test, or a base for which N fails a property that every prime of that form must have (Fermat's little theorem, Euler's criterion or the Lucas condition).

In the last case the report gives Res64. The test ends with a residue, a number between 0 and N-1 of about the same size as N: a^((N-1)/2) mod N in a Proth or Pépin test, the last term of the sequence in a Lucas-Lehmer or LLR test, a multiple of U(N+1) in the N+1 test, or a^(N-1) mod N when Fermat's test fails. For a prime that residue would have a fixed value (-1, 0 or 1), so any other value proves that N is composite. Res64 is a short fingerprint of the residue: its last 64 bits, written as 16 hexadecimal digits (for example 33CBBC3A5D663ADF).

It serves to check the result independently: another program that performs the same test with the same base and the same residue must print the same Res64. Large searches have long double-checked their composites this way (GIMPS, for instance, compared the Res64 of two independent Lucas-Lehmer runs). Programs that use a different base or a different residue, such as PFGW with its default settings, may print a different value even though they also find N composite.

Numbers that are not admissible

An absolute proof with these theorems needs a large known factored part of N-1 or N+1. For numbers without that structure (repunits, Wagstaff numbers (2^p+1)/3, Fibonacci and Leyland numbers, or arbitrary numbers) a proof requires either an extensive factorization of N-1 and N+1, when one can be found, or general methods such as ECPP (for instance Marcel Martin's Primo). Both are far beyond what a browser calculator can do for large numbers, so in those cases the calculator explains why it does not apply instead of giving a probable-prime answer.

Why this calculator

To our knowledge, no other tool on the web gives absolute primality proofs for numbers of these forms with tens or hundreds of thousands of digits, together with the complete proof, using nothing but a browser. General-purpose online tools either stop at a few thousand digits for a true proof, or report "prime" after probable-prime tests such as Fermat, Miller-Rabin or BPSW. Those tests are extremely reliable, but they are not proofs. Until a number has passed an absolute test, whether one of the eight theorems used here or a general method such as ECPP, the proper term is probable prime (PRP). For numbers of the eight forms above, this calculator turns a PRP into a proven prime in about the time a probable-prime test takes.