Primality Testing — confirming a number is prime without factoring it

Primality testing decides whether n is prime without factoring it — the gate you run before trusting that a modulus, a generated candidate, or a factor you just found is actually prime.

The signal that gives it away

You reach for this whenever a challenge hands you a number and either its primality is *assumed* or you need to *verify* it before the next step is valid:

- You factored or guessed a candidate value and must confirm it's genuinely prime before using it (e.g. as one of two RSA prime factors) rather than a composite that happens to share a common structure. - A challenge script generates its own "random primes" — worth checking whether it actually validates them, or just trusts a weak/partial test (a classic seeded-in bug). - A modulus or parameter is *claimed* prime in the challenge text or code comments, and that claim is exactly the kind of assumption CTF authors like to quietly break — a "prime" that's actually a composite Carmichael Numbers & λ(n) — the true group exponent, and why a lone Fermat test lies (Fermat-test-fooling) breaks any downstream reasoning built on it. - You need to decide whether Legendre or Jacobi Symbol — the factoring-free residuosity bit, and why +1 lies on a composite modulus math applies — Legendre requires a genuinely prime modulus, so you confirm primality first. - You suspect n is a prime power rather than a prime (see Perfect-Power Modulus (n = p^k) — trivial factoring via integer k-th root) — a naive test that only answers "prime or not" can mislead you if what you actually needed was "is this p^k".

How to exploit

Miller–Rabin is the workhorse. Probabilistic, O(k log³n) for k rounds, error probability at most `4^-k` (not 2^-k — that weaker bound belongs to the related Solovay–Strassen test, see below). In practice:

1. For cryptographic-size candidates, don't hand-roll it — use sympy.isprime(n) or SageMath's Integer(n).is_prime(). Both combine strong Miller–Rabin rounds with a Lucas-style test (the Baillie–PSW construction), which has no known counterexample despite being unproven in general — strictly stronger in practice than plain Miller–Rabin with a handful of bases. 2. If you need provable (not just probable) primality — e.g. the challenge is adversarial about edge cases — use Pocklington's criterion or ECPP: is_prime(proof=True) in SageMath. 3. Fixed small-base sets are deterministic only below specific, known bounds — this is worth getting exactly right rather than assuming "the usual 12 bases cover everything up to ~10^24": - bases {2,3,5,7,11,13,17,19,23,29,31,37} (12 bases) are deterministic for n < 2^64 (18,446,744,073,709,551,616) — the bound most tools and references cite, and the one worth assuming if you're not chasing the tightest possible number. Sorenson & Webster (2015) proved the *same* 12 bases actually stay deterministic much further, up to n < 318,665,857,834,031,151,167,461 (~3.2·10^23); don't rely on that tighter figure unless you've confirmed your library implements the Sorenson–Webster result rather than just the 2^64 cutoff. - Extending to base 41 (13 bases total) pushes the deterministic bound to n < 3,317,044,064,679,887,385,961,981 (~3.3·10^24). - Mixing these up — quoting a bound past 2^64 while only actually testing through base 37, or without knowing whether your specific tool relies on the conservative or the Sorenson–Webster bound — silently reintroduces a probabilistic gap right at the boundary you thought was covered. If your candidate is anywhere near these magnitudes, check which base set *and* which bound your tool actually relies on before trusting a "deterministic" verdict.

``python def miller_rabin(n, bases=(2,3,5,7,11,13,17,19,23,29,31,37,41)): if n < 2: return False d, r = n - 1, 0 while d % 2 == 0: d //= 2; r += 1 for a in bases: if a % n == 0: continue x = pow(a, d, n) if x in (1, n - 1): continue for _ in range(r - 1): x = x * x % n if x == n - 1: break else: return False return True ``

For anything beyond a quick script, prefer the library call — it already picks a safe strategy for the input size:

``python from sympy import isprime isprime(n) # BPSW-backed, effectively deterministic in practice for CTF-sized n ``

What does NOT work

- A lone Fermat test (`a^(n-1) ≡ 1 mod n`). It's fooled outright by Carmichael Numbers & λ(n) — the true group exponent, and why a lone Fermat test lies — composites (561 is the smallest) that pass Fermat's check for *every* base coprime to n. Never trust "passes Fermat once" or even "passes Fermat for several random bases" as a primality proof; always require the strong (Miller–Rabin) variant, which no composite can fool for all bases simultaneously. - Solovay–Strassen as a drop-in replacement for Miller–Rabin. It's a legitimate, older probabilistic test built on the Jacobi Symbol — the factoring-free residuosity bit, and why +1 lies on a composite modulus (a^((n-1)/2) ≡ (a/n) mod n), but its per-round error bound is only 2^-k, weaker than Miller–Rabin's 4^-k — for the same confidence you need roughly twice the rounds. There's no reason to reach for it over Miller–Rabin/BPSW in a CTF context; it mainly shows up as background theory, not as the tool you actually run. - Assuming "not obviously prime" means "composite and therefore factorable the easy way." A number can be composite yet still resist trial division, Fermat, and even weak Miller–Rabin runs if you use too few rounds or bad bases — a failed cursory check is not evidence either way. Run enough rounds (or just call the library function) before concluding anything. - Treating "is_prime returns True" as "is exactly `p`, not a prime power in disguise." Standard primality tests answer "is n prime", not "is n of the form p^k" — if the challenge's n is actually a perfect power (n = p^k, k > 1), a prime test on n itself correctly says "composite", but the interesting structure (and the fast integer-root break) is specific to that case; don't stop at "not prime" without checking Perfect-Power Modulus (n = p^k) — trivial factoring via integer k-th root when the size or generation code looks suspicious. - Skipping the check because "the challenge probably generated real primes." CTF crypto challenges routinely plant a broken generator (low entropy, a Carmichael number slipped in, a prime power mislabeled as prime) precisely because it's easy to *assume* primality and move on — verifying costs one function call and closes off an entire class of wrong assumptions downstream.

Related

Carmichael Numbers & λ(n) — the true group exponent, and why a lone Fermat test lies Jacobi Symbol — the factoring-free residuosity bit, and why +1 lies on a composite modulus Legendre Symbol — the O(log p) yes/no on square-root existence, before you touch Tonelli-Shanks Perfect-Power Modulus (n = p^k) — trivial factoring via integer k-th root Integer Factorization Methodology — which factoring attack to try, in what order RSA Fundamentals — the routing hub: which artifact points to which attack