Pollard's p−1 factorization
Finds a factor of a composite number when one of its primes p has a smooth p − 1: 1003 with a bound of 16 splits into 17 and 59, since 17 − 1 is 16. If nothing appears, raise the bound. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- N
- 1003
- Bound
- 16
- Factor
- 17
- Cofactor
- 59
- Base
- 2
Pollard's p minus one method is a classical integer factorization algorithm that finds a nontrivial factor of a composite modulus n when at least one prime factor p of n has the property that p minus one is smooth with respect to a chosen bound B — meaning every prime power in the factorization of p minus one is at most B. Students of elementary number theory, CTF competitors, and cryptography learners meet this algorithm when they study why RSA moduli must avoid primes with smooth totients. This capability runs a deterministic stage-one Pollard's p−1 search: it builds the product of prime powers up to B, raises a small base to that exponent modulo n, and returns gcd of that power minus one with n whenever the gcd is a proper factor.
How Pollard's p−1 finds a factor from a smooth p−1
Fix a composite integer n and a positive smoothness bound B. Pollard's observation is simple: if p is a prime divisor of n and every prime power dividing p minus one is at most B, then the least common multiple of the integers one through B is a multiple of p minus one.
By Fermat's little theorem, any base a coprime to p satisfies a to the power of p minus one congruent to one modulo p, and therefore a raised to that large lcm is also congruent to one modulo p. Computing the same power modulo n and taking the greatest common divisor of the result minus one with n often yields p or another nontrivial factor.
In practice the implementation never builds the full lcm explicitly; it sieves the primes up to B and, for each prime q, raises the running accumulator to the highest power of q that does not exceed B, all modulo n. After each prime power step it evaluates gcd of the accumulator minus one with n. An intermediate nontrivial gcd returns immediately.
If the gcd collapses to n itself, a finer recovery walk over smaller exponents tries to isolate a single prime factor before giving up on that base. Several small bases are tried so that unlucky orders for base two do not hide an otherwise B-smooth factor. The method is not a complete factorization algorithm: it returns one nontrivial factor and the matching cofactor.
Callers who need a full prime factorization can feed each composite piece into a prime factorization tool or raise B and run again. Success is guaranteed only in the smooth p−1 setting; large prime factors of p minus one force a larger B or a different algorithm such as the elliptic curve method or quadratic sieve.
When this factoring method pays off
Cryptography courses use Pollard's p−1 to show students why primes with smooth predecessors are dangerous in RSA and Diffie–Hellman parameter generation; a live tool that accepts n and B lets instructors demonstrate a split in class without writing modular exponentiation by hand. Capture-the-flag and homework platforms need a deterministic oracle that either returns a documented factor for classic semiprimes such as one thousand three with bound sixteen, or rejects undersized bounds so graders can mark both correct factors and correct failure reasoning.
Security engineers auditing legacy key generation can screen candidate moduli for p−1 smooth factors before those moduli ever reach production. Keep n within the digit limit, choose B large enough to cover the largest prime factor of p minus one for some prime p dividing n, and you get reproducible factors for teaching, CTF write-ups, and lightweight audits without standing up a full computer-algebra stack.
What you can do with it
Modulus hygiene checks
Screen candidate RSA or Diffie–Hellman moduli for factors with smooth p−1 before deployment without importing a full factorization suite.
FAQ
What is Pollard's p−1 factorization method?
It is a stage-one algorithm that computes a large smooth power of a base modulo n and returns gcd(a^M − 1, n). It finds a factor p when p−1 is B-smooth for the chosen bound B.
When does the method fail to find a factor?
When n is prime, when every prime factor p of n has a prime divisor of p−1 larger than B, or when recovery cannot isolate a proper factor.
Does it return the complete prime factorization?
No. It returns one nontrivial factor and the cofactor n/factor (smaller first). Factor each piece further with a prime factorization tool if you need all prime powers.
Which bound should I choose?
Start small and raise it if no factor appears. The bound has to cover every prime power in p − 1 for at least one prime factor p of your number. Any whole number from 2 to 50,000 is accepted.
How many digits can the number have?
Up to 18 digits, written as a plain whole number without commas or spaces. Even numbers return the factor 2 straight away, and a prime number gives no factor because there is nothing to split.
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/pollard-p-minus-one \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":"1003","bound":16}'const res = await fetch("https://api.kit.forhosting.com/numth/pollard-p-minus-one", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": "1003",
"bound": 16
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/pollard-p-minus-one",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": "1003",
"bound": 16
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/pollard-p-minus-one", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":"1003","bound":16}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":"1003","bound":16}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/pollard-p-minus-one", 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": "1003",
"bound": 16
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.pollard_p_minus_one",
"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
When the bound is too tight, n is prime, or every factor resists the method, the task fails with invalid_input instead of inventing a factor. The free browser path and the paid API share the same pure BigInt module so homework checks and automation never disagree.
Input contract, response shape, and failure modes
Field n is the integer to factor: a safe JavaScript integer or a plain decimal string without commas, spaces, or scientific notation, at least two and at most eighteen decimal digits. Example: n equals one thousand three and bound equals sixteen returns factor seventeen and cofactor fifty-nine because seventeen minus one equals sixteen, which is sixteen-smooth. If n is even the factor two is returned immediately without a full stage-one search. POST a JSON object with two required fields. Field bound is the smoothness bound B, an integer from two through fifty thousand; aliases B, b, smoothness_bound, and smoothness are accepted for convenience. On success the body echoes n as a decimal string and bound as an integer, then reports factor and cofactor as decimal strings with the smaller factor first, the base that produced the factor, and method set to the fixed string pollard_p_minus_one. Missing fields, non-integers, n below two, bound outside the published range, and n longer than eighteen digits fail with invalid_input and are not billed.
Where a p−1 factor API earns its keep
Notebook authors who already have a general prime factorization routine still benefit from an explicit p−1 endpoint when the lesson is the method itself rather than the complete factor list.
Integration use cases
Classroom demos of smooth p−1
Show how a bound B that covers p−1 for one prime factor of a semiprime yields a nontrivial split, using classic examples such as n=1003 with B=16.
CTF and homework auto-graders
Grade Pollard's p−1 exercises with a deterministic oracle that returns the factor when B is sufficient and invalid_input when the bound is too tight.
Technical questions
What inputs does the API require?
Field n (integer ≥ 2, ≤ 18 digits) and field bound (smoothness B from 2 to 50000). Aliases include number/value for n and B/smoothness_bound for bound.
What does Pollard's p−1 factorization cost?
The browser tool is free. API requests use prepaid KIT balance at $0.002 per successful call; invalid input and failed bounds are not billed.