Solovay-Strassen primality test with a chosen base
For 13 with base 2, both residues come out as 12, so 13 passes and is a probable prime to base 2. A mismatch would prove the number composite, with the base as the witness. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- N
- 13
- First text
- 2
- Gcd
- 1
- Jacobi symbol
- -1
- Euler residue
- 12
- Expected residue
- 12
The Solovay-Strassen primality test checks whether an odd integer behaves like a prime for one base selected by the user. It computes the Jacobi symbol of the base modulo the candidate, raises that base to half of the candidate minus one, and compares the two values modulo the candidate. The result identifies a definite composite witness or reports that the number is a probable prime to that base. Inputs are decimal strings, preserving large integers exactly instead of subjecting them to floating-point rounding.
What the comparison means
For an odd prime n and any base a that is not divisible by n, Euler's criterion says that a raised to the power (n - 1) / 2 is congruent modulo n to the Legendre symbol of a. The Jacobi symbol extends the symbol calculation to odd composite candidates, which makes it inexpensive to compute without knowing the factorization of n. Solovay-Strassen compares the modular power with the Jacobi symbol represented as a residue: 1 stays 1, while -1 becomes n - 1.
A mismatch is mathematical proof that n is composite. A match is weaker. Testing a different valid base can expose a composite number that happened to pass the first comparison.
Choosing and validating the inputs
Supply n and a as unsigned decimal strings. The candidate n must be odd and at least three; even values and smaller values produce an invalid-input error because they fall outside this test's stated domain. The base must satisfy 1 < a < n.
It does not need to be coprime in advance: the capability calculates gcd(a, n), and a nontrivial common factor immediately makes the candidate composite. Each input is limited to 1,000 decimal digits so modular arithmetic has a clear, enforced computational bound. Leading signs, whitespace, decimal points, exponent notation, and leading zeroes are rejected rather than interpreted ambiguously.
When selecting a base manually, use more than one distinct base for stronger evidence. A base is not chosen randomly by this capability, which keeps every execution reproducible and lets callers record precisely which witness was checked in an audit or teaching example.
Reading the result responsibly
The passes field answers whether the exact Solovay-Strassen congruence holds for the supplied pair. When it is false, classification is composite and the supplied base is a certificate that the candidate cannot be prime. Repeat the test with independently selected bases if Solovay-Strassen is required by an existing exercise or protocol, and treat every passing round as additional probabilistic evidence rather than proof.
For new security-sensitive systems, use a modern, carefully specified primality-testing procedure with an appropriate set of rounds and reviewed randomness instead of treating a single manually chosen base as sufficient.
What you can do with it
Check a textbook witness
Reproduce a Solovay-Strassen exercise with the exact candidate and base stated in the problem.
Inspect pseudoprime behavior
Compare how a composite candidate passes for one base and fails for another while retaining every intermediate value.
Build a reproducible screening step
Record deterministic single-base results before applying additional bases or a stronger primality procedure.
FAQ
Does a passing result prove that n is prime?
No. It means only that n is a probable prime to the supplied base; another base may prove it composite.
Why must n be odd and at least three?
The Jacobi-symbol comparison used by this test is defined here for odd candidates at least three.
What happens when a and n share a factor?
The returned gcd exposes the common factor and the test classifies n as composite without treating the Jacobi comparison as a pass.
Does the capability choose a random base?
No. The caller supplies the base, making the computation deterministic and reproducible.
How large can the numbers in a Solovay-Strassen test be?
Each number can have up to 1,000 decimal digits. Both are handled exactly as typed, with no rounding, so a very large candidate gets the same exact comparison as a small one.
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/solovay-strassen-test \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":"561","a":"2"}'const res = await fetch("https://api.kit.forhosting.com/numth/solovay-strassen-test", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": "561",
"a": "2"
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/solovay-strassen-test",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": "561",
"a": "2"
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/solovay-strassen-test", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":"561","a":"2"}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":"561","a":"2"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/solovay-strassen-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": "561",
"a": "2"
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.solovay_strassen_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.
Limits
max_digits | 1000 |
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
What the comparison means
It says only that n passed for this chosen base, so the output uses the careful classification probable_prime_to_base. The response includes both residues, the Jacobi value, and their greatest common divisor so the decision remains inspectable rather than appearing as an unexplained Boolean result.
Choosing and validating the inputs
String input matters because ordinary JSON numbers cannot exactly represent every large integer.
Reading the result responsibly
When it is true, classification is probable_prime_to_base, not prime. The detailed fields help diagnose each outcome: gcd shows an immediately shared factor, jacobi_symbol is -1, 0, or 1, euler_residue is the computed modular power, and expected_residue is the Jacobi value normalized into the range modulo n. API requests use the published base price placeholder $0.002; the same deterministic calculation can also support interactive browser use.
Technical questions
Why are n and a strings instead of JSON numbers?
Decimal strings preserve integers exactly beyond JavaScript's safe numeric range and prevent silent rounding.
How much does an API request cost?
The base charge is $0.002 per request. One request evaluates one candidate-base pair.