Pocklington primality test
Proves a number prime from a partial factorization of n − 1: for 31, the primes 2, 3 and 5 of 30 give a factored part of 30, and since 900 is at least 31, one witness per prime certifies it. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- N
- 31
- Factors
- 2, 3, 5
- N
- 31
- N minus 1
- 30
- F
- 30
- R
- 1
The Pocklington–Lehmer criterion turns a partial factorization of n minus one into a rigorous primality certificate. Unlike trial division alone or a single Fermat congruence, it needs only enough of n−1 factored so that the factored part F satisfies F squared at least n, plus a short modular witness for each prime dividing F. Students, crypto tutors, and number-theory notebooks use this Pocklington primality test to prove small and medium primes without sieving up to the square root of n. You supply the candidate n and the primes that multiply to F; the engine checks the size bound, searches or verifies bases a, and returns a structured certificate or a clear error when the factored part is too small.
What the Pocklington–Lehmer criterion states
Write n minus one as the product F times R, where F is completely factored into primes you already know and R is the remaining cofactor.
The classical Pocklington theorem says: if F is large enough that F squared is at least n, and for every prime q dividing F there exists an integer base a such that a raised to the power n minus one is congruent to one modulo n, and the greatest common divisor of a raised to (n minus one) over q, minus one, with n, equals one, then n must be prime.
Intuitively, those two modular conditions force the multiplicative order of a modulo n to be a multiple of q for each such prime, so the order is a multiple of F; combined with F being larger than the square root of n, no composite n can hide a proper factor in the usual way. This is stronger than Fermat’s little theorem alone, which only checks a single power residue and can be fooled by pseudoprimes.
It is also more economical than full factorization of n or trial division up to sqrt(n) when you already know many factors of n−1—for example when n is a Proth number, a safeprime construction, or a homework integer built so that n−1 factors easily. This capability implements that exact checklist: product of your factors becomes F, R is (n−1)/F, the size gate F² ≥ n is enforced, and each distinct prime q of F gets a witness a (auto-searched from two upward, or taken from your optional bases list).
What you can do with it
Homework and exam primality certificates
Students factor n−1, submit n and the primes of F, and receive witnesses proving n is prime under Pocklington–Lehmer when F is large enough.
Contest and LMS auto-graders
Mark number-theory items with a deterministic certificate oracle that rejects too-small F and non-prime factor lists instead of silent false positives.
FAQ
What is the Pocklington primality test?
A criterion that certifies n is prime from a partial factorization n−1=F·R with F fully factored, F²≥n, and modular witnesses a for each prime q dividing F.
When is the factored part too small?
When F² < n (equivalently F ≤ R for the split n−1=F·R).
What inputs do I send?
Required n (≥3) and factors (array of primes with multiplicity multiplying to F).
Does certified false mean n is composite?
No. It means no valid witness was found under the given F and bases. n may still be prime; try more bases or a larger factored part, or another primality method.
Can I choose the witness bases myself?
Yes. List whole numbers of at least 2, either one base shared by every prime or one per distinct prime in order. If you leave them out, the test searches bases from 2 through 200 on its own.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
curl -X POST https://api.kit.forhosting.com/numth/pocklington-test \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":31,"factors":[2,3,5]}'const res = await fetch("https://api.kit.forhosting.com/numth/pocklington-test", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 31,
"factors": [
2,
3,
5
]
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/pocklington-test",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 31,
"factors": [
2,
3,
5
]
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/pocklington-test", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":31,"factors":[2,3,5]}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":31,"factors":[2,3,5]}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/pocklington-test", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"n": 31,
"factors": [
2,
3,
5
]
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.pocklington_test",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
The same pure BigInt logic powers the free browser tool and the API path at $0.002 per successful request.
What the Pocklington–Lehmer criterion states
When every prime passes, the response sets certified and is_prime to true and lists the witnesses so you can re-check the arithmetic by hand or in another system.
Input contract, size errors, and reading the certificate
Example: n equals thirty-one and factors equals two, three, five because thirty equals two times three times five; then F is thirty, R is one, and F squared far exceeds thirty-one. Optional bases is an array of integers at least two—either one shared witness for every prime, or one witness per distinct prime in sorted order—or omit it and the engine searches a from two through two hundred. If the product F does not divide n−1, the task fails because the partial factorization is inconsistent. If F squared is strictly less than n, the task fails with a message that the factored part is too small—that is the intentional hard error when you have not factored enough of n−1 to apply Pocklington–Lehmer. POST a JSON body with required integer n (at least three) and required array factors: the prime factors, with multiplicity, of the factored part F of n−1. Each listed factor must itself be prime; composite entries fail with invalid_input so a forged factor list cannot pretend to be a certificate. Successful responses echo n, n_minus_1, F, R, F_squared, floor_sqrt_n, the distinct primes, the multiset of factors, and a witnesses array with per-prime a, the power residue, the gcd check, and ok flags. The boolean certified is true only when every prime has a valid witness; is_prime mirrors certified here because a full Pocklington pass is a primality proof, while a failed witness search does not prove compositeness by itself. Pricing is a flat $0.002 per successful call on the item unit; validation failures are not billed. Large integers may be sent as decimal strings within the published digit limit so JSON never truncates them.
Classroom proofs, crypto demos, and automation
Number-theory courses use a Pocklington primality test so learners can certify primes like thirty-one, sixty-one, or ninety-seven once they factor n−1 by hand, instead of only running a black-box is-prime button. Library authors writing property tests assert that certified true implies their own primality routine agrees on the same n, and that insufficient F always raises the documented too-small error. Contest-prep tools generate candidates with smooth n−1, feed the known factors into this endpoint, and store the returned witnesses as a short proof object next to the answer key. Keep n and factors inside the digit and length limits, prefer string integers for values beyond JavaScript safe integers, and treat certified as the authoritative boolean for “Pocklington proved prime.” When you only have a tiny slice of n−1 factored, factor more first or use a general primality checker; this landing stays dedicated to the Pocklington–Lehmer search intent so SEO, examples, and the response shape remain focused.
Integration use cases
Crypto and CAS notebook checks
Pin golden Pocklington certificates for fixed primes in unit tests without reimplementing modPow and gcd checks in every language.
Technical questions
What does the Pocklington primality test cost?
The browser tool is free. API requests use prepaid KIT balance at $0.002 per successful call; invalid input is never charged.