Fooling Fixed-Basis Miller-Rabin (Arnault Strong Pseudoprimes)

Updated 13 Sep 2026

• •

  What it is

  • •

    The Miller-Rabin primality test is only a probabilistic guarantee against randomly chosen witness bases; many implementations instead test against a small, fixed set of bases for speed and determinism. François Arnault showed this shortcut can be deliberately defeated: it's possible to construct a composite "strong pseudoprime" that passes Miller-Rabin for every base in a chosen fixed set, built as a product of specially-related primes ($p_1$​, $p_2 = k_2(p_1{-}1){+}1$, $p_3 = k_3(p_1{-}1){+}1$, ... for carefully chosen small multipliers $k_i$​) whose relationship guarantees the strong-pseudoprime condition holds simultaneously for every test base, via a mix of quadratic-residue constraints (mod $4a$ for each basis prime $a$) and CRT. The full construction is intricate — see Arnault's original paper, and the "Prime and Prejudice: Primality Testing Under Adversarial Conditions" paper this challenge is named after, for the rigorous derivation. High-level shape: pick multipliers $k_1{=}1, k_2, k_3$​; for each small basis prime $a$, determine which residues mod $4a$ make $a$ a certificate-passing witness against each $k_i$​-shifted version of the candidate; intersect these residue sets across all multipliers; CRT-combine a value satisfying every constraint (plus fixed relations tying $k_2, k_3$​ together); search upward from that CRT solution, in steps of the combined modulus, until $p_1, p_2, p_3$ are all simultaneously prime and their product falls in the target bit-length range.

• •

  When to apply

  • •

    A service accepts an attacker-supplied "prime" and runs Miller-Rabin against a small, fixed, disclosed set of bases (rather than random or a cryptographically-endorsed base set) before trusting it for something security-sensitive.

• •

  Math

  • •

    For each small basis prime $a$ in the fixed test set, and each multiplier $k_i$​, the residue constraints (mod $4a$) are chosen precisely so the strong-pseudoprime (Miller-Rabin) witness condition is satisfied for base $a$ against the final composite $n = p_1 p_2 p_3$​, despite $n$ being composite.

• •

  Worked example

  • •

    Using multipliers $k = [1, 998244353, 233]$ against a fixed test-basis of all primes below 64, backtracking over the intersected residue sets and CRT-combining found a triple of primes whose product is a ~600-900 bit strong pseudoprime that passes miller_rabin(n, 64) in the challenge's own verifier — despite nn n being a product of three known, smaller primes.

• •

  Python

  • •

    Only the shape of the search loop is straightforward; the residue-set construction itself is the intricate part (see the referenced paper):

  • •

    # for each fixed test-basis prime a: build the set of residues mod 4a for
    # which a acts as a passing witness against a p1-candidate for each k_i
    # intersect these sets across k1, k2, k3; CRT-combine a solution
    # satisfying every constraint + the k2/k3 tie relations
    p1 += ((2**(TARGET_BITLEN // 3 + 3) - p1) // mod) * mod
    while True:
        p2 = ks[1] * (p1 - 1) + 1
        p3 = ks[2] * (p1 - 1) + 1
        if is_prime(p1) and is_prime(p2) and is_prime(p3):
            n = p1 * p2 * p3
            assert miller_rabin(n, 64)     # fools the fixed-basis check
            break
        p1 += mod
    

• •

  SageMath

  • •

    Sage's `crt()`, `next_prime()`, `is_prime()`, and `legendre_symbol()` make the backtracking search and CRT-combination substantially less code than a hand-rolled version — the more polished public solve for this challenge leans on exactly these Sage builtins.
    

• •

  Cards

  • •

    Why is testing primality against a small, fixed set of bases weaker than testing against random bases?

    • •

      A fixed set is a known, public target — an attacker can specifically engineer a composite number that passes Miller-Rabin for exactly that set, which isn't possible against unpredictable random bases.

  • •

    What's the general shape of an Arnault strong pseudoprime?

    • •

      A product of several primes related by small integer multipliers (p_i = k_i(p_1-1)+1), chosen via quadratic-residue and CRT constraints so the composite passes the strong-pseudoprime test for every base in the target fixed set.

◌ Explore connections in Graph view