Number Theory II: Primality, Factoring & Discrete Logs
Is prime? Trial division would try about odd divisors up to its square root. Miller–Rabin answers with certainty in 12 modular exponentiations: about a thousand modular multiplications.
What are the prime factors of ? Trial division would need about steps to reach the smaller factor. Pollard's rho (the version in this lesson) finds it after 28,670 steps, using almost no memory.
Given , what is ? Trying every takes up to steps. Baby-step giant-step takes about , and that square root is why your browser uses 2048-bit numbers for Diffie–Hellman and not 64-bit ones.
This lesson is the second number-theory lesson. Number Theory Basics covered divisibility, gcd, the sieve and trial division. Modular Arithmetic covered fast exponentiation, inverses, Fermat's little theorem and the Chinese remainder theorem. Here we use those tools to build the three algorithms every serious number-theory library has: a primality test, a factoring algorithm and a discrete-logarithm solver. Then we finish with the counting side of number theory: multiplicative functions, Möbius inversion and the divisor-block trick for sums like in .
Why this exists
The sieve of Eratosthenes answers "is prime?" for every up to about (memory is the limit). Trial division answers it for a single up to about – (time is the limit: divisions). Past that, both are hopeless, yet real systems need answers for numbers far bigger:
- Cryptography. RSA key generation needs random 1024-bit primes. It draws random odd numbers and tests each one. A 1024-bit number has a 512-bit square root. Trial division is not an option; a probabilistic test is.
- Hashing and randomized algorithms. Polynomial hashing, universal hashing and Rabin–Karp all want a large prime modulus. Choosing a fresh random prime per run (to defeat adversarial inputs, see String Hashing) needs a fast test.
- Competitive programming. "Factor these numbers up to ", "count divisors of ", "find the order of modulo " all need Miller–Rabin plus Pollard's rho.
- Public-key security analysis. The security of Diffie–Hellman, DSA and ElGamal rests on the discrete logarithm being hard. To understand why parameters are 2048 bits and why the group order must have a large prime factor, you need BSGS and Pohlig–Hellman.
A little history. Fermat's little theorem (1640) gave the first fast "compositeness" test, but certain composites (Carmichael numbers, first found by Robert Carmichael in 1910) fool it completely. Gary Miller (1976) found a stronger test that is deterministic if the generalized Riemann hypothesis holds; Michael Rabin (1980) turned it into an unconditional randomized test with error at most . John Pollard published his rho factoring method in 1975 and Richard Brent sped it up in 1980; Brent and Pollard used it to factor the eighth Fermat number . Daniel Shanks described baby-step giant-step in 1971. In 2002 Agrawal, Kayal and Saxena (AKS) proved primality is in deterministic polynomial time, but AKS is far slower in practice than Miller–Rabin, which is what every library actually runs.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "is prime?" with up to (or ) | Deterministic Miller–Rabin with the 12 prime bases |
| "is prime?" with | Miller–Rabin with bases |
| "factor " with up to | Trial divide small primes, then Pollard's rho + Miller–Rabin recursively |
| "number of divisors / sum of divisors / " for one huge | Factor with Pollard's rho, then use the multiplicative formulas |
| "find with " | Baby-step giant-step, |
| "find with " (discrete root) | Primitive root , write , BSGS for , then a linear congruence in |
| "generator", "primitive root", "element of order " | Factor ; test for each prime |
| NTT modulus like | Primitive root 3; see FFT & NTT |
| "count pairs with ", "count square-free numbers" | Möbius function and inclusion–exclusion over divisors |
| ", recover " | Möbius inversion |
| "" or any sum with , | Divisor blocks: only distinct values |
| "cycle", "two pointers chasing in a sequence " | Floyd's or Brent's cycle detection (the "rho" shape) |
Intuition & first principles
Proving "composite" without finding a factor
A surprising fact powers this whole lesson: you can be certain a number is composite without knowing any of its factors.
Fermat's little theorem says: if is prime and is not a multiple of , then . Flip it around. If you find an with , then cannot be prime. Such an is called a witness for 's compositeness. Computing takes multiplications with fast exponentiation, so checking one witness is cheap even for 1000-bit .
Try , : , so 341 is composite. We never divided by anything. (Indeed .)
The problem is the other direction. With : . Base 2 is a liar for 341: it says "looks prime". A composite that passes for base is called a Fermat pseudoprime to base . There are 78 base-2 Fermat pseudoprimes below . Still, trying a few more bases usually catches them. Usually.
The numbers that fool everyone: Carmichael numbers
. Check every base from 1 to 560 that shares no factor with 561 — there are of them. All 320 satisfy . The only bases that expose 561 are those that share a factor with it, and finding one of those is as hard as factoring.
Composites like this are Carmichael numbers. Korselt's criterion (1899) explains them: is Carmichael exactly when is square-free and for every prime . For 561: , , . ✓ So for any coprime to 561, , , , and by the CRT .
The Carmichael numbers below 20,000 are 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841. Alford, Granville and Pomerance proved in 1994 that there are infinitely many. So the plain Fermat test is broken in principle, not just unlucky.
The fix: square roots of 1
Miller's idea adds one more fact about primes:
Modulo a prime , the only square roots of 1 are and .
Proof: means . A prime dividing a product divides one of the factors, so or .
Modulo a composite, there are more square roots of 1. Modulo 561, , so , yet . Such an is a non-trivial square root of 1, and finding one is a smoking gun: it proves composite, and even gives a factor. Here and .
Now combine this with Fermat. Write with odd. Then
Look at the chain . If is prime the chain ends at 1 (Fermat). Walk backwards from the end: each element is a square root of the next one. The first time the chain becomes 1, the element before it is a square root of 1 that is not 1, so for a prime it must be . Therefore, for prime , either the chain starts at 1, or appears somewhere before the last position. A base for which neither happens is a strong witness.
A tiny example you can hold in your head
(prime), . , so , .
Chain: .
It hits , as a prime must. Pass.
, . , so , .
| Step | Value | Meaning |
|---|---|---|
| 263 | not , keep squaring | |
| 166 | not | |
| 67 | not | |
| 1 | became 1 without passing through |
The chain reached 1 at the last step (so Fermat passes: ) but the step before was 67, a non-trivial square root of 1. Base 2 is a strong witness. 561 is composite. Of the 560 bases from 1 to 560, only 10 are strong liars for 561 (1, 50, 101, 103, 256, 305, 458, 460, 511, 560), compared with 320 Fermat liars.
Mechanics
1. The Miller–Rabin test
graph TD
A["n odd, n > 3: write n-1 = 2^s * d, d odd"] --> B["pick base a"]
B --> C["x = a^d mod n"]
C --> D{"x == 1 or x == n-1?"}
D -->|"yes"| P["a says: probably prime"]
D -->|"no"| E["square x, up to s-1 times"]
E --> F{"x == n-1 at some point?"}
F -->|"yes"| P
F -->|"no"| W["a is a witness: n is COMPOSITE (certain)"]
P --> G{"more bases?"}
G -->|"yes"| B
G -->|"no"| H["answer: prime (certain for the fixed base sets below)"]
One-sided error. "Composite" is always correct: a witness is a proof. "Prime" is correct with high probability for random bases, and with certainty for the fixed base sets in the next section when is below their bound.
How often does a random base lie? Rabin (1980) and Monier (1980) proved: for odd composite , at most of the bases in are strong liars. So independent random bases all lie with probability at most . With that is below . The bound is tight: has exactly 2 strong liars (1 and 8) among its 8 bases. For most composites the true fraction is far smaller; for random large odd numbers the probability of error is astronomically below (Damgård, Landrock and Pomerance, 1993).
2. Deterministic base sets: no randomness for 64-bit
For bounded , mathematicians have searched for the smallest composite that fools a given set of bases. If is below that number, testing those bases is a proof.
| Bases | Correct for all below | Source |
|---|---|---|
| 2,047 ( fools base 2) | Pomerance, Selfridge, Wagstaff (1980) | |
| 25,326,001 | Pomerance, Selfridge, Wagstaff (1980) | |
| 3,215,031,751 | Pomerance, Selfridge, Wagstaff (1980) | |
| 4,759,123,141 | Jaeschke (1993) | |
| first 11 primes | Jiang and Deng (2014) | |
| first 12 primes | conjectured by Jiang and Deng (2014); proved by Sorenson and Webster (2017) | |
| first 13 primes | Sorenson and Webster (2017) |
Every entry in the "below" column is itself the smallest composite that fools all the listed bases; our test scripts confirm each one passes every base in its set and fails the next prime base. Since lies between and , the first 12 primes are the smallest prime-base set that covers all 64-bit integers. The 11-prime set is not enough: fits in 64 bits and fools bases 2 through 31. Base 37 catches it.
The three-base and seven-base tricks
For 32-bit inputs, bases are enough: three exponentiations. For 64-bit inputs there are also hand-searched non-prime base sets; the best known is the seven bases {2, 325, 9375, 28178, 450775, 9780504, 1795265022} found by Jim Sinclair (2011) and published on the miller-rabin.appspot.com tables of best known base sets. Twelve prime bases are easier to remember and plenty fast.
Base
With fixed bases, small can be smaller than the base (testing with ). Then may be 0, and would wrongly call composite. The simplest fix, used in all code below: first check divisibility by every base prime. If is one of them, it is prime; if one divides , it is composite. After that, and every base is smaller than .
3. Multiplying 64-bit numbers modulo
The innermost operation, with , needs a 128-bit intermediate product. Every language handles that differently:
| Language | How to get for 64-bit |
|---|---|
| Python | Native big integers: x * y % n; pow(a, d, n) is built in |
| C++ (GCC/Clang) | (unsigned __int128)x * y % n |
| Java | BigInteger (modPow, multiply().mod()), or Math.multiplyHigh plus a hand-written 128/64 reduction; for some people use "Russian peasant" doubling |
| TypeScript/JavaScript | BigInt: x * y % n (numbers lose exactness above ) |
Montgomery multiplication avoids the expensive division altogether and is what fast libraries use; see Modular Arithmetic for the idea.
4. Pollard's rho: finding a factor by waiting for a collision
Once Miller–Rabin says "composite", we want a factor. Pollard's insight uses the birthday paradox.
The birthday intuition. Pick random numbers from . After about picks you expect two to be equal (the same reason that 23 people likely share a birthday; see Probability for Engineers). Now suppose and we generate numbers modulo . We cannot see the values modulo (we don't know ), but they are there. After about steps, two values are likely equal modulo while still different modulo . Then , so is a multiple of but (usually) not : a factor.
Since the smallest prime factor of a composite is at most , about steps suffice. For a 64-bit , that is around steps in the worst case, versus for trial division.
Why "rho". Use a pseudo-random sequence instead of truly random numbers. The key property: is a polynomial, so implies . Once the sequence repeats modulo , it cycles forever. Drawn on paper, a tail followed by a loop looks like the Greek letter .
Take , , :
| 0 | 2 | 2 | 2 |
| 1 | 5 | 5 | 5 |
| 2 | 26 | 26 | 26 |
| 3 | 677 | 95 | 13 |
| 4 | 7474 | 5 | 4 |
| 5 | 2839 | 26 | 17 |
| 6 | 871 | 95 | 41 |
| 7 | 1848 | 5 | 22 |
Modulo 97 the sequence is : a tail of length 1 and a cycle of length 3. Modulo 83 it is still wandering (its cycle, , starts at index 4 and has length 5).
graph LR
X0["x0 = 2"] --> X1["x1 = 5"]
X1 --> X2["x2 = 26"]
X2 --> X3["x3 = 95 (mod 97)"]
X3 -->|"x4 = 5 again"| X1
Floyd's cycle detection (tortoise and hare). We cannot store all values and look for a repeat modulo an unknown . Instead, run two pointers: the tortoise takes one step (), the hare takes two (). Once both are inside the cycle, the hare gains one position per step, so it lands on the tortoise (modulo ) within one cycle length. Check after each step. This is the same algorithm that finds a cycle in a linked list (see Linked Lists).
Dry run on 8051:
| Step | Tortoise | Hare | ||
|---|---|---|---|---|
| 1 | 5 | 26 | 21 | 1 |
| 2 | 26 | 7474 | 7448 | 1 |
| 3 | 677 | 871 | 194 | 97 |
At step 3, and . The gcd reveals 97, and . Three steps; trial division would have needed 41 odd divisors.
Brent's improvement. Floyd evaluates three times per step. Richard Brent (1980) keeps the tortoise fixed at positions (powers of two) and lets the hare run steps from it, comparing against the saved value; then doubles . Each step costs one evaluation of . Brent reported his variant about 24% faster on average than Pollard's original.
Batching the gcds. A gcd costs multiplications-worth of work; a step of costs one. So instead of a gcd per step, multiply values together modulo for, say, 128 steps and take one gcd of the product. If any of them shares the factor , the product does too. If the product overshoots (the gcd is because two factors were caught in the same batch, or the product became 0), back up to the start of the batch and redo it one step at a time. This makes the gcd cost negligible.
When rho fails. If both prime factors cycle at the same moment, the gcd is itself. Then restart with a different constant in . (Avoid and : those polynomials have special structure and cycle badly.) Rho also "fails" on prime by never finding anything, which is why you always run Miller–Rabin first.
Deeper: the is heuristic
The analysis treats as a random function. Nobody has proved it behaves that way, but decades of experiments agree with the prediction of about steps to enter the cycle and for the cycle length (Knuth, TAOCP Vol. 2, §4.5.4). Bach (1991) proved a weaker rigorous bound for a related version. In practice, for 64-bit inputs, it is the fastest simple method by a wide margin.
5. Full 64-bit factorization
Putting the pieces together:
graph TD
A["factor(n)"] --> B{"n == 1?"}
B -->|"yes"| R["return"]
B -->|"no"| C["trial-divide small primes (say up to 100)"]
C --> D{"is_prime(n) by Miller-Rabin?"}
D -->|"yes"| E["record n as a prime factor"]
D -->|"no"| F["d = pollard_rho(n)"]
F --> G["factor(d)"]
F --> H["factor(n / d)"]
Examples computed by the code in this lesson:
| Prime factorization | |
|---|---|
| prime | |
| (the hard case: two primes near ) | |
| (Project Euler #3) |
For the record, the Pollard–Brent code below evaluates 28,670 times to split the hard case, 1,662 times for , and 510 times for . The hardest 64-bit inputs for rho are balanced semiprimes (two primes of about 32 bits each), because then is as large as it gets. Numbers with a small factor are dispatched by trial division; numbers whose cofactor is prime stop after one Miller–Rabin.
6. Discrete logarithm: baby-step giant-step
The problem. Given a prime , a base and a target , find with . This is the discrete logarithm of to base . "Discrete" because there is no smooth curve to follow: for jumps around as .
By Fermat, , so exponents repeat with period dividing . Brute force tries : .
The meet-in-the-middle idea. Pick . Any in can be written as with . Then
- Baby steps: compute and store each value in a hash table. multiplications.
- Giant steps: compute and look each up in the table. The first hit at giant step with stored gives . At most multiplications and lookups.
Total time and memory, using a hash table. It is the same meet-in-the-middle trade as in Divide and Conquer: split one search of size into two of size that meet.
Trace. Solve . .
Baby steps ():
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 1 | 2 | 4 | 8 | 16 | 3 |
Giant step factor: . Since and , the factor is 5.
| In table? | ||
|---|---|---|
| 0 | 22 | no |
| 1 | 23 | no |
| 2 | 28 | no |
| 3 | 24 | no |
| 4 | 4 | yes, |
. Check: . ✓
graph LR
subgraph baby["baby steps: g^j stored in a hash map"]
B0["1 (j=0)"] --> B1["2 (j=1)"] --> B2["4 (j=2)"] --> B3["8"] --> B4["16"] --> B5["3"]
end
subgraph giant["giant steps: h times g^-m, repeatedly"]
G0["22"] --> G1["23"] --> G2["28"] --> G3["24"] --> G4["4: hit at i=4"]
end
G4 -.->|"matches j=2"| B2
Smallest answer, and no answer. Iterating upward and keeping the smallest for each stored value returns the smallest . If does not generate everything, some have no logarithm: modulo 7, only takes the values , so has no solution and BSGS correctly returns "none" after giant steps.
Deeper: composite moduli and generic lower bounds
For composite and , the plain method breaks because has no inverse. The standard fix strips common factors one at a time (cp-algorithms, "Discrete Logarithm"), reducing to a coprime instance plus a small offset. More fundamentally, Shoup (1997) proved that any generic algorithm (one that only multiplies group elements and compares them, without looking at their representation) needs group operations, where is the largest prime factor of the group order. So BSGS and Pollard's rho for logarithms are optimal among generic algorithms. Faster algorithms (index calculus) exploit the fact that elements of are integers that can be factored.
7. Primitive roots
A primitive root modulo a prime is a whose powers hit every non-zero residue exactly once. Equivalently, the order of (the smallest with ) is exactly . Modulo 7, 3 is a primitive root: . 2 is not: , order 3.
Every prime has primitive roots, of them (Gauss). More generally, primitive roots exist modulo exactly when is or for an odd prime .
Testing a candidate. The order of divides (Lagrange). If the order is a proper divisor, it divides for some prime . So:
Finding one. Factor (Pollard's rho if needed), then try . Primitive roots are dense enough that the smallest one is tiny in practice (Shoup proved a bound polynomial in under GRH). Example, , :
| Primitive? | |||
|---|---|---|---|
| 2 | 1 | 4 | no (order 11) |
| 3 | 1 | 9 | no (order 11) |
| 4 | 1 | 16 | no (order 11) |
| 5 | 22 | 2 | yes |
Known values the tests confirm: smallest primitive root of is 5; of it is 3; of it is 13.
Why you want one. With a primitive root , every non-zero residue is for a unique . That turns multiplication into addition of exponents, so equations like (discrete roots) become linear congruences . It is also how NTT picks its roots of unity: has order exactly .
8. Pohlig–Hellman, index calculus, and why Diffie–Hellman needs big safe primes
Diffie–Hellman key exchange (Diffie and Hellman, 1976) lets two parties agree on a secret over a public channel. Public: prime , generator . Alice picks secret and sends . Bob picks secret and sends . Both compute : Alice as , Bob as . Toy example with , , , : , , shared secret .
An eavesdropper sees . If they could compute discrete logs, they would get and the secret. So DH is at most as hard as the discrete log, and every DL algorithm is an attack:
- BSGS / Pollard's rho for logs: . For a 64-bit that is steps: seconds. For a 2048-bit , : impossible. This is why toy-sized DH is insecure.
- Pohlig–Hellman (1978): if the group order , solve the log modulo each separately (in a subgroup of that size) and glue with the CRT. The cost is about , so it depends on the largest prime factor of , not on . Example: , so logs modulo this famous NTT prime are trivial no matter how they are hidden. Defence: use a safe prime with prime (the RFC 7919 groups for TLS are safe primes), or work in a prime-order subgroup.
- Index calculus: pick a "factor base" of small primes, find many that factor over it (smooth numbers), solve a linear system for the logs of the small primes, then express any target. It runs in sub-exponential time, about ; the number field sieve improves this to . These only work because elements of are integers with factorizations. Elliptic-curve groups have no known analogue, which is why 256-bit elliptic-curve keys (X25519) match about 3072-bit classic DH.
- Precomputation (Logjam, 2015). Most of the number field sieve's work depends only on , not on the target. Adrian et al. showed that with a week of precomputation for a common 512-bit "export" prime, individual logs took a minute or two, and estimated that a nation-state could do the same for a widely shared 1024-bit prime. Lesson: avoid small and widely shared groups.
Hardness of DL is a conjecture, not a theorem; Shor's quantum algorithm (1994) solves both factoring and DL in polynomial time on a large quantum computer, which is the motivation for post-quantum key exchange (ML-KEM). For how this is used in practice see Cryptography for Engineers, Symmetric vs Asymmetric Encryption and Cryptography in the Real World.
9. Multiplicative functions
An arithmetic function is multiplicative if and whenever . Then is determined by its values on prime powers: if , then . Factor once, evaluate everything.
| Function | Meaning | On | Example: |
|---|---|---|---|
| or | number of divisors | ||
| sum of divisors | |||
| count of coprime to | |||
| Möbius function | if , if |
So with Pollard's rho you get , , for any in milliseconds. For all at once, a linear sieve (see Number Theory Basics) computes any multiplicative function in .
10. The Möbius function and Möbius inversion
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | −1 | −1 | 0 | −1 | 1 | −1 | 0 | 0 | 1 | −1 | 0 | |
| 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 |
The key identity. if , else . Why: if has distinct primes, the square-free divisors are subsets of those primes, and . This is inclusion–exclusion in disguise (see Combinatorics): supplies the alternating signs over sets of primes.
Möbius inversion. If for all , then
Proof sketch: substitute and swap sums; the inner sum kills every term except . Example: Gauss's identity inverts to . For : (the divisors 4 and 12 have ). ✓
Counting coprime pairs. How many pairs with have ? Replace "" by and swap sums:
For : 63; for : 6087. (Both match brute force.) The fraction tends to : two random integers are coprime about 61% of the time.
Deeper: Dirichlet convolution
Define . It is commutative and associative, and the convolution of multiplicative functions is multiplicative. With , and : , , , . Möbius inversion is just "convolve both sides with ". Sums like for are computed in about with these identities plus divisor blocks (the "Dirichlet hyperbola" and Du's sieve techniques; cp-algorithms and Codeforces blogs cover them).
11. Divisor blocks: in
Let . It equals (each divides numbers up to ). Summing term by term is ; for that is too slow.
Observation: takes at most distinct values. For there are at most choices of ; for the value , so at most values. And each value occupies one contiguous block of : if , the last with the same quotient is .
For , the values for are :
| Block | Contribution | ||
|---|---|---|---|
| [1, 1] | 10 | 1 | 10 |
| [2, 2] | 5 | 2 | 5 |
| [3, 3] | 3 | 3 | 3 |
| [4, 5] | 2 | 5 | 4 |
| [6, 10] | 1 | 10 | 5 |
Total 27. The loop:
def divisor_sum_blocks(n: int) -> int:
total, i = 0, 1
while i <= n:
q = n // i
j = n // q # last i with the same quotient
total += q * (j - i + 1)
i = j + 1
return total
assert divisor_sum_blocks(10) == 27
assert divisor_sum_blocks(100) == 482 # = d(1) + ... + d(100)
assert divisor_sum_blocks(10**12) == 27785452449086
The same blocking works for any sum when prefix sums of are cheap: for example (CSES "Sum of Divisors") uses the arithmetic-series formula for each block, and the coprime-pair count above uses prefix sums of to jump over blocks of .
def mobius_sieve(n: int) -> list[int]:
mu = [1] * (n + 1)
is_comp = [False] * (n + 1)
primes: list[int] = []
for i in range(2, n + 1):
if not is_comp[i]:
primes.append(i)
mu[i] = -1
for p in primes:
if i * p > n:
break
is_comp[i * p] = True
if i % p == 0:
mu[i * p] = 0 # p^2 divides i*p
break
mu[i * p] = -mu[i]
return mu
def coprime_pairs(n: int) -> int:
mu = mobius_sieve(n)
pref = [0] * (n + 1)
for i in range(1, n + 1):
pref[i] = pref[i - 1] + mu[i]
total, d = 0, 1
while d <= n: # divisor blocks over d
q = n // d
e = n // q
total += (pref[e] - pref[d - 1]) * q * q
d = e + 1
return total
assert mobius_sieve(12)[1:] == [1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0]
assert coprime_pairs(10) == 63 and coprime_pairs(100) == 6087
The ladder: brute force → better → optimal
Primality of one number
| Rung | Method | Time | Certain? | Practical limit |
|---|---|---|---|---|
| 1 | Trial division up to | yes | ||
| 2 | Fermat test, bases | multiplications | no: Carmichael numbers fool every coprime base | — (don't) |
| 3 | Miller–Rabin, random bases | multiplications | error | any size |
| 4 | Miller–Rabin, fixed 12 bases | yes, for | all 64-bit | |
| 5 | Baillie–PSW (one base-2 strong test + a strong Lucas test) | about 3 Miller–Rabin rounds | no known counterexample; none below | what GMP, PARI and Mathematica use |
| side | AKS | yes, unconditionally | theory only |
Rung 2 → 3 fixes the Carmichael hole with the square-root-of-1 check. Rung 3 → 4 removes randomness by using known pseudoprime searches. For huge numbers where a proof is required (certificates), ECPP (elliptic curve primality proving) is used instead of AKS.
Factoring one number
| Rung | Method | Time (to find smallest factor ) | Memory | Good for |
|---|---|---|---|---|
| 1 | Trial division | , or any with a small factor | ||
| 2 | Pollard's | fast if is smooth | special-shape factors | |
| 3 | Pollard's rho (Floyd) | expected, heuristic | 64-bit | |
| 4 | Pollard–Brent with batched gcd | same, about 2–3× fewer operations | 64-bit , the standard choice | |
| 5 | Elliptic curve method (ECM), quadratic sieve, number field sieve | sub-exponential | large | 30–250+ digit numbers (research and cryptanalysis) |
Discrete log modulo a prime
| Rung | Method | Time | Memory |
|---|---|---|---|
| 1 | Try every | ||
| 2 | Baby-step giant-step | ||
| 3 | Pollard's rho for logarithms | expected | |
| 4 | Pohlig–Hellman | for | small |
| 5 | Index calculus / number field sieve | sub-exponential | large |
Correctness
Miller–Rabin never calls a prime composite. Let be an odd prime and . By Fermat, . Let be the smallest index with . If , the chain starts at 1: pass. Otherwise satisfies and , so (only square roots of 1 modulo a prime), and appears at index : pass. So every base passes for a prime.
Error bound (sketch). For composite , the strong liars are contained in a proper subgroup of (or a union of cosets) whose size, by a counting argument over the CRT components, is at most for . The full proof splits into the cases " is a prime power", " has at least three prime factors" and "" (Crandall and Pomerance, Prime Numbers, §3.5). Random independent bases multiply the failure probabilities: .
Deterministic bases. No proof is needed beyond the published exhaustive searches: for below (the smallest strong pseudoprime to all of ), no composite passes all 12 bases, and all 64-bit integers are below it.
Pollard's rho returns a proper factor when it returns. It only returns with , which divides by definition of gcd. Termination with high probability follows from the birthday argument modulo the smallest prime , heuristically. The batched version is correct because iff some prime of divides some ; the fallback replays the batch individually to avoid returning when several primes were caught at once.
Factorization is complete. Induction on : if is prime, record it (correct by Miller–Rabin). Otherwise rho returns , and factor(), factor() are correct by induction on smaller inputs; the multiset union is the factorization of by unique factorization.
BSGS returns the smallest solution or correctly reports none. Every has a unique representation with , and covers a full period of . iff , which the table lookup tests exactly. Scanning upward, and storing the smallest for each baby value, means the first hit has the smallest and then the smallest : the smallest . If no hits, no in a full period works, so no solution exists.
Primitive-root test. If , then and , so some prime divides , and , giving . Contrapositive: if no such exists, the order is .
Divisor blocks. For fixed , the set is the interval , so is its right end and the loop visits each interval once.
Complexity
Let be the cost of one multiplication modulo : for 64-bit with 128-bit hardware products, bit operations schoolbook for big numbers.
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| Miller–Rabin, bases | 12 bases × about 64 squarings for 64-bit | ||
| Pollard–Brent, one factor | expected (heuristic), = smallest prime factor | ||
| Full factorization of 64-bit | expected, dominated by the largest rho call | for the factor list | at most 15 distinct primes below |
| BSGS | multiplications + hash operations | memory is the practical limit: needs entries | |
| Primitive root | factor , then | = number of distinct prime factors | |
| Möbius / any multiplicative function, all | linear sieve | ||
| Divisor-block sum |
Best, average, worst. Miller–Rabin on a prime always does all rounds (worst case); on a random composite it usually exits after the first base. Pollard's rho on with a tiny factor is near-instant; balanced semiprimes are the worst case. BSGS's worst case is with no logarithm (full giant steps).
Implementation
Three code groups: Miller–Rabin (with the Fermat test for comparison), Pollard–Brent factorization, and BSGS with primitive roots. Each block runs its own checks. Python, C++ and TypeScript handle all of ; the Java versions use long and therefore accept (they use BigInteger for the 128-bit products, as the lesson brief suggests; Math.multiplyHigh with a Montgomery or Barrett reduction is the faster production route).
Miller–Rabin, deterministic for 64-bit
from math import gcd
BASES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) # deterministic for n < 3.2e23
def is_strong_probable_prime(n: int, a: int) -> bool:
"""One Miller-Rabin round: True if base a does NOT prove odd n > 2 composite."""
d, s = n - 1, 0
while d % 2 == 0: # n - 1 = 2^s * d with d odd
d //= 2
s += 1
x = pow(a, d, n)
if x == 1 or x == n - 1:
return True
for _ in range(s - 1):
x = x * x % n
if x == n - 1:
return True
return False # a is a witness: n is composite
def is_prime(n: int) -> bool:
if n < 2:
return False
for p in BASES: # handles small n and makes every base < n
if n % p == 0:
return n == p
return all(is_strong_probable_prime(n, a) for a in BASES)
def fermat_probable_prime(n: int, a: int) -> bool:
return pow(a, n - 1, n) == 1
def sieve(limit: int) -> list[bool]:
is_p = [True] * (limit + 1)
is_p[0] = is_p[1] = False
for i in range(2, int(limit**0.5) + 1):
if is_p[i]:
is_p[i * i :: i] = [False] * len(is_p[i * i :: i])
return is_p
if __name__ == "__main__":
primes = [2, 3, 37, 41, 1_000_000_007, 998_244_353, 2**61 - 1, 10**18 + 3,
10**18 + 9, 9_223_372_036_854_775_783, 18_446_744_073_709_551_557]
composites = [0, 1, 4, 561, 1105, 1729, 2047, 25_326_001, 3_215_031_751,
4_759_123_141, 3_825_123_056_546_413_051, 10**18 + 1, 10**18 + 7,
2**64 - 1, 999_999_937 * 1_000_000_007]
assert all(is_prime(p) for p in primes)
assert not any(is_prime(c) for c in composites)
# 561 fools Fermat for every coprime base, but base 2 is a strong witness
assert all(fermat_probable_prime(561, a) for a in range(2, 561) if gcd(a, 561) == 1)
assert not is_strong_probable_prime(561, 2)
assert sum(is_strong_probable_prime(561, a) for a in range(1, 561)) == 10
# the famous pseudoprimes behind the deterministic base tables
assert is_strong_probable_prime(2047, 2)
assert all(is_strong_probable_prime(3_215_031_751, a) for a in (2, 3, 5, 7))
assert all(is_strong_probable_prime(4_759_123_141, a) for a in (2, 7, 61))
big = 3_825_123_056_546_413_051
assert all(is_strong_probable_prime(big, a) for a in BASES[:-1]) # 2..31 all lie
assert not is_strong_probable_prime(big, 37) # 37 catches it
ref = sieve(200_000)
assert all(is_prime(i) == ref[i] for i in range(200_001))
print("Miller-Rabin: all checks passed")
import java.math.BigInteger;
public class Main {
static final long[] BASES = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
static long mulMod(long a, long b, long m) { // 128-bit product via BigInteger
return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b))
.mod(BigInteger.valueOf(m)).longValue();
}
static long powMod(long a, long e, long m) {
return BigInteger.valueOf(a).modPow(BigInteger.valueOf(e), BigInteger.valueOf(m))
.longValue();
}
/** One Miller-Rabin round for odd n > 2: true if base a does NOT prove n composite. */
static boolean isStrongProbablePrime(long n, long a) {
long d = n - 1;
int s = 0;
while ((d & 1) == 0) { d >>= 1; s++; }
long x = powMod(a, d, n);
if (x == 1 || x == n - 1) return true;
for (int i = 1; i < s; i++) {
x = mulMod(x, x, n);
if (x == n - 1) return true;
}
return false;
}
/** Deterministic for every 0 <= n <= Long.MAX_VALUE. */
static boolean isPrime(long n) {
if (n < 2) return false;
for (long p : BASES) if (n % p == 0) return n == p;
for (long a : BASES) if (!isStrongProbablePrime(n, a)) return false;
return true;
}
static boolean fermatProbablePrime(long n, long a) { return powMod(a, n - 1, n) == 1; }
static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
static void check(boolean cond, String msg) { if (!cond) throw new AssertionError(msg); }
public static void main(String[] args) {
long[] primes = {2, 3, 37, 41, 1_000_000_007L, 998_244_353L, (1L << 61) - 1,
1_000_000_000_000_000_003L, 1_000_000_000_000_000_009L, 9_223_372_036_854_775_783L};
long[] composites = {0, 1, 4, 561, 1105, 1729, 2047, 25_326_001L, 3_215_031_751L,
4_759_123_141L, 3_825_123_056_546_413_051L, 1_000_000_000_000_000_001L,
1_000_000_000_000_000_007L, Long.MAX_VALUE, 999_999_937L * 1_000_000_007L};
for (long p : primes) check(isPrime(p), "prime " + p);
for (long c : composites) check(!isPrime(c), "composite " + c);
int strongLiars = 0;
for (long a = 1; a < 561; a++) {
if (gcd(a, 561) == 1) check(fermatProbablePrime(561, a), "561 Fermat");
if (isStrongProbablePrime(561, a)) strongLiars++;
}
check(strongLiars == 10, "561 strong liars");
long big = 3_825_123_056_546_413_051L;
for (int i = 0; i < 11; i++) check(isStrongProbablePrime(big, BASES[i]), "base lies");
check(!isStrongProbablePrime(big, 37), "37 catches it");
int limit = 200_000;
boolean[] comp = new boolean[limit + 1];
for (int i = 2; (long) i * i <= limit; i++)
if (!comp[i]) for (int j = i * i; j <= limit; j += i) comp[j] = true;
for (int i = 0; i <= limit; i++) check(isPrime(i) == (i >= 2 && !comp[i]), "sieve " + i);
System.out.println("Miller-Rabin: all checks passed");
}
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
using u64 = std::uint64_t;
using u128 = unsigned __int128;
const u64 BASES[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
u64 mul_mod(u64 a, u64 b, u64 m) { return (u128)a * b % m; }
u64 pow_mod(u64 a, u64 e, u64 m) {
u64 r = 1;
a %= m;
while (e) {
if (e & 1) r = mul_mod(r, a, m);
a = mul_mod(a, a, m);
e >>= 1;
}
return r;
}
// One Miller-Rabin round for odd n > 2: true if base a does NOT prove n composite.
bool is_strong_probable_prime(u64 n, u64 a) {
u64 d = n - 1;
int s = 0;
while ((d & 1) == 0) { d >>= 1; ++s; }
u64 x = pow_mod(a, d, n);
if (x == 1 || x == n - 1) return true;
for (int i = 1; i < s; ++i) {
x = mul_mod(x, x, n);
if (x == n - 1) return true;
}
return false;
}
bool is_prime(u64 n) { // deterministic for all 64-bit n
if (n < 2) return false;
for (u64 p : BASES) if (n % p == 0) return n == p;
for (u64 a : BASES) if (!is_strong_probable_prime(n, a)) return false;
return true;
}
bool fermat_probable_prime(u64 n, u64 a) { return pow_mod(a, n - 1, n) == 1; }
int main() {
std::vector<u64> primes = {2, 3, 37, 41, 1000000007ULL, 998244353ULL, (1ULL << 61) - 1,
1000000000000000003ULL, 1000000000000000009ULL,
9223372036854775783ULL, 18446744073709551557ULL};
std::vector<u64> composites = {0, 1, 4, 561, 1105, 1729, 2047, 25326001ULL, 3215031751ULL,
4759123141ULL, 3825123056546413051ULL,
1000000000000000001ULL, 1000000000000000007ULL,
18446744073709551615ULL, 999999937ULL * 1000000007ULL};
for (u64 p : primes) assert(is_prime(p));
for (u64 c : composites) assert(!is_prime(c));
int strong_liars = 0;
for (u64 a = 1; a < 561; ++a) {
if (std::gcd(a, (u64)561) == 1) assert(fermat_probable_prime(561, a));
if (is_strong_probable_prime(561, a)) ++strong_liars;
}
assert(strong_liars == 10);
u64 big = 3825123056546413051ULL;
for (int i = 0; i < 11; ++i) assert(is_strong_probable_prime(big, BASES[i]));
assert(!is_strong_probable_prime(big, 37));
const int LIMIT = 200000;
std::vector<bool> comp(LIMIT + 1, false);
for (int i = 2; (long long)i * i <= LIMIT; ++i)
if (!comp[i]) for (int j = i * i; j <= LIMIT; j += i) comp[j] = true;
for (int i = 0; i <= LIMIT; ++i) assert(is_prime(i) == (i >= 2 && !comp[i]));
std::cout << "Miller-Rabin: all checks passed\n";
}
const BASES: bigint[] = [2n, 3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n, 31n, 37n];
function powMod(a: bigint, e: bigint, m: bigint): bigint {
let r = 1n;
a %= m;
while (e > 0n) {
if (e & 1n) r = (r * a) % m;
a = (a * a) % m;
e >>= 1n;
}
return r;
}
/** One Miller-Rabin round for odd n > 2: true if base a does NOT prove n composite. */
function isStrongProbablePrime(n: bigint, a: bigint): boolean {
let d = n - 1n;
let s = 0;
while ((d & 1n) === 0n) { d >>= 1n; s++; }
let x = powMod(a, d, n);
if (x === 1n || x === n - 1n) return true;
for (let i = 1; i < s; i++) {
x = (x * x) % n;
if (x === n - 1n) return true;
}
return false;
}
function isPrime(n: bigint): boolean {
if (n < 2n) return false;
for (const p of BASES) if (n % p === 0n) return n === p;
return BASES.every((a) => isStrongProbablePrime(n, a));
}
const fermatProbablePrime = (n: bigint, a: bigint): boolean => powMod(a, n - 1n, n) === 1n;
function gcd(a: bigint, b: bigint): bigint { return b === 0n ? a : gcd(b, a % b); }
function assert(cond: boolean, msg: string): void { if (!cond) throw new Error(msg); }
const primes = [2n, 3n, 37n, 41n, 1_000_000_007n, 998_244_353n, 2n ** 61n - 1n, 10n ** 18n + 3n,
10n ** 18n + 9n, 9_223_372_036_854_775_783n, 18_446_744_073_709_551_557n];
const composites = [0n, 1n, 4n, 561n, 1105n, 1729n, 2047n, 25_326_001n, 3_215_031_751n,
4_759_123_141n, 3_825_123_056_546_413_051n, 10n ** 18n + 1n, 10n ** 18n + 7n, 2n ** 64n - 1n,
999_999_937n * 1_000_000_007n];
for (const p of primes) assert(isPrime(p), `prime ${p}`);
for (const c of composites) assert(!isPrime(c), `composite ${c}`);
let strongLiars = 0;
for (let a = 1n; a < 561n; a++) {
if (gcd(a, 561n) === 1n) assert(fermatProbablePrime(561n, a), "561 Fermat");
if (isStrongProbablePrime(561n, a)) strongLiars++;
}
assert(strongLiars === 10, "561 strong liars");
const big = 3_825_123_056_546_413_051n;
assert(BASES.slice(0, 11).every((a) => isStrongProbablePrime(big, a)), "bases 2..31 lie");
assert(!isStrongProbablePrime(big, 37n), "37 catches it");
const LIMIT = 50_000;
const comp = new Uint8Array(LIMIT + 1);
for (let i = 2; i * i <= LIMIT; i++) if (!comp[i]) for (let j = i * i; j <= LIMIT; j += i) comp[j] = 1;
for (let i = 0; i <= LIMIT; i++) assert(isPrime(BigInt(i)) === (i >= 2 && !comp[i]), `sieve ${i}`);
console.log("Miller-Rabin: all checks passed");
Pollard–Brent rho and full factorization
import random
from math import gcd
BASES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)
BATCH = 128
def is_prime(n: int) -> bool:
if n < 2:
return False
for p in BASES:
if n % p == 0:
return n == p
d, s = n - 1, 0
while d % 2 == 0:
d //= 2
s += 1
for a in BASES:
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(s - 1):
x = x * x % n
if x == n - 1:
break
else:
return False
return True
def pollard_brent(n: int) -> int:
"""Return a factor 1 < d < n of a composite n."""
if n % 2 == 0:
return 2
c = 1
while True:
def f(v: int) -> int:
return (v * v + c) % n
y, r, q, g = 2, 1, 1, 1
x = ys = y
while g == 1:
x = y # tortoise parks at positions 1, 2, 4, 8, ...
for _ in range(r):
y = f(y)
k = 0
while k < r and g == 1:
ys = y # remember the batch start for the fallback
for _ in range(min(BATCH, r - k)):
y = f(y)
q = q * abs(x - y) % n # multiply differences, one gcd per batch
g = gcd(q, n)
k += BATCH
r *= 2
if g == n: # overshoot: replay the batch one step at a time
g = 1
while g == 1:
ys = f(ys)
g = gcd(abs(x - ys), n)
if g != n:
return g
c += 1 # unlucky polynomial: try x^2 + (c + 1)
def factorize(n: int) -> list[int]:
"""Sorted prime factors of n >= 1, with multiplicity."""
out: list[int] = []
for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47):
while n % p == 0:
out.append(p)
n //= p
stack = [n] if n > 1 else []
while stack:
m = stack.pop()
if is_prime(m):
out.append(m)
else:
d = pollard_brent(m)
stack += [d, m // d]
return sorted(out)
if __name__ == "__main__":
assert factorize(8051) == [83, 97]
assert factorize(2**64 - 1) == [3, 5, 17, 257, 641, 65537, 6700417]
assert factorize(10**18 + 1) == [101, 9901, 999999000001]
assert factorize(10**18 + 7) == [1370531, 729644203597]
assert factorize(10**18 + 9) == [10**18 + 9]
assert factorize(999_999_937 * 1_000_000_007) == [999_999_937, 1_000_000_007]
assert factorize(2**62 - 1) == [3, 715827883, 2147483647]
assert factorize(600851475143) == [71, 839, 1471, 6857]
assert factorize(3_825_123_056_546_413_051) == [149491, 747451, 34233211]
assert factorize((2**31 - 1) ** 2) == [2**31 - 1, 2**31 - 1]
assert factorize(1) == [] and factorize(2**63) == [2] * 63
def trial(n: int) -> list[int]:
out, p = [], 2
while p * p <= n:
while n % p == 0:
out.append(p)
n //= p
p += 1
return out + ([n] if n > 1 else [])
assert all(factorize(n) == trial(n) for n in range(1, 30_001))
rng = random.Random(2026)
for _ in range(300):
n = rng.randrange(2, 2**64)
fs = factorize(n)
prod = 1
for p in fs:
prod *= p
assert prod == n and all(is_prime(p) for p in fs)
print("Pollard-Brent: all checks passed")
import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
public class Main {
static final long[] BASES = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
static final int BATCH = 128;
static long mulMod(long a, long b, long m) {
return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b))
.mod(BigInteger.valueOf(m)).longValue();
}
static long powMod(long a, long e, long m) {
return BigInteger.valueOf(a).modPow(BigInteger.valueOf(e), BigInteger.valueOf(m))
.longValue();
}
static boolean isPrime(long n) { // deterministic, 0 <= n < 2^63
if (n < 2) return false;
for (long p : BASES) if (n % p == 0) return n == p;
long d = n - 1;
int s = 0;
while ((d & 1) == 0) { d >>= 1; s++; }
outer:
for (long a : BASES) {
long x = powMod(a, d, n);
if (x == 1 || x == n - 1) continue;
for (int i = 1; i < s; i++) {
x = mulMod(x, x, n);
if (x == n - 1) continue outer;
}
return false;
}
return true;
}
static long gcd(long a, long b) { while (b != 0) { long t = a % b; a = b; b = t; } return a; }
/** A factor 1 < d < n of composite n (Brent's cycle detection, batched gcd). */
static long pollardBrent(long n) {
if (n % 2 == 0) return 2;
for (long c = 1; ; c++) {
long y = 2, x = 2, ys = 2, q = 1, g = 1;
int r = 1;
while (g == 1) {
x = y;
for (int i = 0; i < r; i++) y = (mulMod(y, y, n) + c) % n;
for (int k = 0; k < r && g == 1; k += BATCH) {
ys = y;
for (int i = 0; i < Math.min(BATCH, r - k); i++) {
y = (mulMod(y, y, n) + c) % n;
q = mulMod(q, Math.abs(x - y), n);
}
g = gcd(q, n);
}
r *= 2;
}
if (g == n) {
g = 1;
while (g == 1) {
ys = (mulMod(ys, ys, n) + c) % n;
g = gcd(Math.abs(x - ys), n);
}
}
if (g != n) return g;
}
}
static List<Long> factorize(long n) {
List<Long> out = new ArrayList<>();
for (long p = 2; p < 50; p++) while (n % p == 0) { out.add(p); n /= p; }
ArrayDeque<Long> stack = new ArrayDeque<>();
if (n > 1) stack.push(n);
while (!stack.isEmpty()) {
long m = stack.pop();
if (isPrime(m)) { out.add(m); continue; }
long d = pollardBrent(m);
stack.push(d);
stack.push(m / d);
}
Collections.sort(out);
return out;
}
static void check(boolean cond, String msg) { if (!cond) throw new AssertionError(msg); }
static void expect(long n, long... factors) {
List<Long> want = new ArrayList<>();
for (long f : factors) want.add(f);
check(factorize(n).equals(want), "factorize " + n + " -> " + factorize(n));
}
public static void main(String[] args) {
expect(8051, 83, 97);
expect(1_000_000_000_000_000_001L, 101, 9901, 999_999_000_001L);
expect(1_000_000_000_000_000_007L, 1_370_531, 729_644_203_597L);
expect(1_000_000_000_000_000_009L, 1_000_000_000_000_000_009L);
expect(999_999_937L * 1_000_000_007L, 999_999_937L, 1_000_000_007L);
expect((1L << 62) - 1, 3, 715_827_883L, 2_147_483_647L);
expect(600_851_475_143L, 71, 839, 1471, 6857);
expect(3_825_123_056_546_413_051L, 149_491, 747_451, 34_233_211);
expect(2_147_483_647L * 2_147_483_647L, 2_147_483_647L, 2_147_483_647L);
expect(Long.MAX_VALUE, 7, 7, 73, 127, 337, 92737, 649657);
check(factorize(1).isEmpty(), "factorize 1");
for (long n = 1; n <= 30_000; n++) { // compare with trial division
List<Long> want = new ArrayList<>();
long m = n;
for (long p = 2; p * p <= m; p++) while (m % p == 0) { want.add(p); m /= p; }
if (m > 1) want.add(m);
check(factorize(n).equals(want), "small " + n);
}
Random rng = new Random(2026);
for (int t = 0; t < 200; t++) {
long n = (rng.nextLong() >>> 1) | 2; // random in [2, 2^63)
long prod = 1;
for (long p : factorize(n)) { check(isPrime(p), "prime factor"); prod *= p; }
check(prod == n, "product " + n);
}
System.out.println("Pollard-Brent: all checks passed");
}
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
using u64 = std::uint64_t;
using u128 = unsigned __int128;
const u64 BASES[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
const u64 BATCH = 128;
u64 mul_mod(u64 a, u64 b, u64 m) { return (u128)a * b % m; }
u64 pow_mod(u64 a, u64 e, u64 m) {
u64 r = 1;
a %= m;
for (; e; e >>= 1, a = mul_mod(a, a, m))
if (e & 1) r = mul_mod(r, a, m);
return r;
}
bool is_prime(u64 n) {
if (n < 2) return false;
for (u64 p : BASES) if (n % p == 0) return n == p;
u64 d = n - 1;
int s = 0;
while ((d & 1) == 0) { d >>= 1; ++s; }
for (u64 a : BASES) {
u64 x = pow_mod(a, d, n);
if (x == 1 || x == n - 1) continue;
bool hit = false;
for (int i = 1; i < s && !hit; ++i) {
x = mul_mod(x, x, n);
hit = (x == n - 1);
}
if (!hit) return false;
}
return true;
}
u64 absdiff(u64 a, u64 b) { return a > b ? a - b : b - a; }
// A factor 1 < d < n of composite n.
u64 pollard_brent(u64 n) {
if (n % 2 == 0) return 2;
for (u64 c = 1;; ++c) {
auto f = [&](u64 v) { return (mul_mod(v, v, n) + c) % n; };
u64 y = 2, x = 2, ys = 2, q = 1, g = 1;
for (u64 r = 1; g == 1; r <<= 1) {
x = y;
for (u64 i = 0; i < r; ++i) y = f(y);
for (u64 k = 0; k < r && g == 1; k += BATCH) {
ys = y;
for (u64 i = 0; i < std::min(BATCH, r - k); ++i) {
y = f(y);
q = mul_mod(q, absdiff(x, y), n);
}
g = std::gcd(q, n);
}
}
if (g == n) {
g = 1;
while (g == 1) {
ys = f(ys);
g = std::gcd(absdiff(x, ys), n);
}
}
if (g != n) return g;
}
}
std::vector<u64> factorize(u64 n) {
std::vector<u64> out;
for (u64 p = 2; p < 50; ++p)
while (n % p == 0) { out.push_back(p); n /= p; }
std::vector<u64> stack;
if (n > 1) stack.push_back(n);
while (!stack.empty()) {
u64 m = stack.back();
stack.pop_back();
if (is_prime(m)) { out.push_back(m); continue; }
u64 d = pollard_brent(m);
stack.push_back(d);
stack.push_back(m / d);
}
std::sort(out.begin(), out.end());
return out;
}
int main() {
using V = std::vector<u64>;
assert(factorize(8051) == (V{83, 97}));
assert(factorize(18446744073709551615ULL) == (V{3, 5, 17, 257, 641, 65537, 6700417}));
assert(factorize(1000000000000000001ULL) == (V{101, 9901, 999999000001ULL}));
assert(factorize(1000000000000000007ULL) == (V{1370531, 729644203597ULL}));
assert(factorize(1000000000000000009ULL) == (V{1000000000000000009ULL}));
assert(factorize(999999937ULL * 1000000007ULL) == (V{999999937, 1000000007}));
assert(factorize((1ULL << 62) - 1) == (V{3, 715827883, 2147483647}));
assert(factorize(600851475143ULL) == (V{71, 839, 1471, 6857}));
assert(factorize(3825123056546413051ULL) == (V{149491, 747451, 34233211}));
assert(factorize(2147483647ULL * 2147483647ULL) == (V{2147483647, 2147483647}));
assert(factorize(1).empty() && factorize(1ULL << 63) == V(63, 2));
for (u64 n = 1; n <= 30000; ++n) {
V want;
u64 m = n;
for (u64 p = 2; p * p <= m; ++p) while (m % p == 0) { want.push_back(p); m /= p; }
if (m > 1) want.push_back(m);
assert(factorize(n) == want);
}
std::mt19937_64 rng(2026);
for (int t = 0; t < 300; ++t) {
u64 n = rng() | 2;
u128 prod = 1;
for (u64 p : factorize(n)) { assert(is_prime(p)); prod *= p; }
assert(prod == n);
}
std::cout << "Pollard-Brent: all checks passed\n";
}
const BASES: bigint[] = [2n, 3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n, 31n, 37n];
const BATCH = 128n;
function powMod(a: bigint, e: bigint, m: bigint): bigint {
let r = 1n;
a %= m;
for (; e > 0n; e >>= 1n, a = (a * a) % m) if (e & 1n) r = (r * a) % m;
return r;
}
function isPrime(n: bigint): boolean {
if (n < 2n) return false;
for (const p of BASES) if (n % p === 0n) return n === p;
let d = n - 1n;
let s = 0;
while ((d & 1n) === 0n) { d >>= 1n; s++; }
return BASES.every((a) => {
let x = powMod(a, d, n);
if (x === 1n || x === n - 1n) return true;
for (let i = 1; i < s; i++) {
x = (x * x) % n;
if (x === n - 1n) return true;
}
return false;
});
}
function gcd(a: bigint, b: bigint): bigint {
while (b !== 0n) [a, b] = [b, a % b];
return a;
}
const absDiff = (a: bigint, b: bigint): bigint => (a > b ? a - b : b - a);
/** A factor 1 < d < n of composite n (Brent's cycle detection, batched gcd). */
function pollardBrent(n: bigint): bigint {
if (n % 2n === 0n) return 2n;
for (let c = 1n; ; c++) {
const f = (v: bigint): bigint => (v * v + c) % n;
let y = 2n, x = 2n, ys = 2n, q = 1n, g = 1n;
for (let r = 1n; g === 1n; r *= 2n) {
x = y;
for (let i = 0n; i < r; i++) y = f(y);
for (let k = 0n; k < r && g === 1n; k += BATCH) {
ys = y;
const steps = BATCH < r - k ? BATCH : r - k;
for (let i = 0n; i < steps; i++) {
y = f(y);
q = (q * absDiff(x, y)) % n;
}
g = gcd(q, n);
}
}
if (g === n) {
g = 1n;
while (g === 1n) {
ys = f(ys);
g = gcd(absDiff(x, ys), n);
}
}
if (g !== n) return g;
}
}
function factorize(n: bigint): bigint[] {
const out: bigint[] = [];
for (let p = 2n; p < 50n; p++) while (n % p === 0n) { out.push(p); n /= p; }
const stack: bigint[] = n > 1n ? [n] : [];
while (stack.length > 0) {
const m = stack.pop() as bigint;
if (isPrime(m)) { out.push(m); continue; }
const d = pollardBrent(m);
stack.push(d, m / d);
}
return out.sort((a, b) => (a < b ? -1 : a > b ? 1 : 0));
}
function expect(n: bigint, want: bigint[]): void {
const got = factorize(n);
if (got.join(",") !== want.join(",")) throw new Error(`factorize ${n} -> ${got}`);
}
expect(8051n, [83n, 97n]);
expect(2n ** 64n - 1n, [3n, 5n, 17n, 257n, 641n, 65537n, 6700417n]);
expect(10n ** 18n + 1n, [101n, 9901n, 999999000001n]);
expect(10n ** 18n + 7n, [1370531n, 729644203597n]);
expect(10n ** 18n + 9n, [10n ** 18n + 9n]);
expect(999_999_937n * 1_000_000_007n, [999_999_937n, 1_000_000_007n]);
expect(2n ** 62n - 1n, [3n, 715827883n, 2147483647n]);
expect(600851475143n, [71n, 839n, 1471n, 6857n]);
expect(3_825_123_056_546_413_051n, [149491n, 747451n, 34233211n]);
expect((2n ** 31n - 1n) ** 2n, [2n ** 31n - 1n, 2n ** 31n - 1n]);
expect(1n, []);
for (let n = 1n; n <= 5000n; n++) {
const want: bigint[] = [];
let m = n;
for (let p = 2n; p * p <= m; p++) while (m % p === 0n) { want.push(p); m /= p; }
if (m > 1n) want.push(m);
expect(n, want);
}
let seed = 2026n;
for (let t = 0; t < 40; t++) {
seed = (seed * 6364136223846793005n + 1442695040888963407n) % 2n ** 64n; // LCG
const n = seed | 2n;
const fs = factorize(n);
if (fs.reduce((a, b) => a * b, 1n) !== n || !fs.every(isPrime)) throw new Error(`random ${n}`);
}
console.log("Pollard-Brent: all checks passed");
Baby-step giant-step and primitive roots
from math import isqrt
def bsgs(g: int, h: int, p: int) -> int:
"""Smallest x >= 0 with g^x = h (mod prime p), or -1 if none."""
g %= p
h %= p
m = isqrt(p - 1) + 1 # m * m > p - 1: covers a full period
table: dict[int, int] = {}
cur = 1
for j in range(m): # baby steps: g^j -> j (keep the smallest j)
table.setdefault(cur, j)
cur = cur * g % p
giant = pow(g, -m, p) # g^(-m) mod p (Python 3.8+)
gamma = h
for i in range(m): # giant steps: h * g^(-i m)
j = table.get(gamma)
if j is not None:
return i * m + j
gamma = gamma * giant % p
return -1
def prime_factors(n: int) -> list[int]:
out, d = [], 2
while d * d <= n:
if n % d == 0:
out.append(d)
while n % d == 0:
n //= d
d += 1
return out + ([n] if n > 1 else [])
def primitive_root(p: int) -> int:
"""Smallest primitive root modulo prime p."""
if p == 2:
return 1
qs = prime_factors(p - 1)
g = 2
while any(pow(g, (p - 1) // q, p) == 1 for q in qs):
g += 1
return g
if __name__ == "__main__":
assert bsgs(2, 22, 29) == 26
assert bsgs(3, 13, 17) == 4
assert bsgs(2, 3, 7) == -1 # 2 only generates {1, 2, 4} mod 7
assert bsgs(5, 1, 23) == 0
P = 1_000_000_007
assert bsgs(5, pow(5, 123_456_789, P), P) == 123_456_789
for p in (7, 11, 13, 29, 101): # brute-force cross-check
for g in range(2, p):
for h in range(1, p):
want = next((x for x in range(p - 1) if pow(g, x, p) == h), -1)
assert bsgs(g, h, p) == want
assert primitive_root(7) == 3 and primitive_root(23) == 5
assert primitive_root(1_000_000_007) == 5
assert primitive_root(998_244_353) == 3
assert primitive_root(1_000_000_009) == 13
g = primitive_root(101)
assert len({pow(g, k, 101) for k in range(1, 101)}) == 100 # hits every residue
print("BSGS and primitive roots: all checks passed")
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;
public class Main {
static long powMod(long a, long e, long m) { // m < 2^31, so products fit in long
long r = 1;
a %= m;
for (; e > 0; e >>= 1, a = a * a % m) if ((e & 1) == 1) r = r * a % m;
return r;
}
/** Smallest x >= 0 with g^x = h (mod prime p < 2^31), or -1 if none. */
static long bsgs(long g, long h, long p) {
g %= p;
h %= p;
long m = (long) Math.sqrt((double) (p - 1)) + 1;
while (m * m <= p - 1) m++;
HashMap<Long, Long> table = new HashMap<>();
long cur = 1;
for (long j = 0; j < m; j++) {
table.putIfAbsent(cur, j);
cur = cur * g % p;
}
long giant = powMod(powMod(g, m, p), p - 2, p); // g^(-m) by Fermat
long gamma = h;
for (long i = 0; i < m; i++) {
Long j = table.get(gamma);
if (j != null) return i * m + j;
gamma = gamma * giant % p;
}
return -1;
}
static List<Long> primeFactors(long n) {
List<Long> out = new ArrayList<>();
for (long d = 2; d * d <= n; d++) {
if (n % d == 0) {
out.add(d);
while (n % d == 0) n /= d;
}
}
if (n > 1) out.add(n);
return out;
}
static long primitiveRoot(long p) {
if (p == 2) return 1;
List<Long> qs = primeFactors(p - 1);
for (long g = 2; ; g++) {
boolean ok = true;
for (long q : qs) if (powMod(g, (p - 1) / q, p) == 1) { ok = false; break; }
if (ok) return g;
}
}
static void check(boolean cond, String msg) { if (!cond) throw new AssertionError(msg); }
public static void main(String[] args) {
check(bsgs(2, 22, 29) == 26, "2^x=22 mod 29");
check(bsgs(3, 13, 17) == 4, "3^x=13 mod 17");
check(bsgs(2, 3, 7) == -1, "no solution");
check(bsgs(5, 1, 23) == 0, "x = 0");
long P = 1_000_000_007L;
check(bsgs(5, powMod(5, 123_456_789, P), P) == 123_456_789, "big p");
for (long p : new long[] {7, 11, 13, 29, 101})
for (long g = 2; g < p; g++)
for (long h = 1; h < p; h++) {
long want = -1;
for (long x = 0; x < p - 1; x++) if (powMod(g, x, p) == h) { want = x; break; }
check(bsgs(g, h, p) == want, "brute " + g + " " + h + " " + p);
}
check(primitiveRoot(7) == 3 && primitiveRoot(23) == 5, "small roots");
check(primitiveRoot(1_000_000_007L) == 5, "1e9+7");
check(primitiveRoot(998_244_353L) == 3, "998244353");
check(primitiveRoot(1_000_000_009L) == 13, "1e9+9");
HashSet<Long> seen = new HashSet<>();
long g = primitiveRoot(101);
for (long k = 1; k <= 100; k++) seen.add(powMod(g, k, 101));
check(seen.size() == 100, "generates everything");
System.out.println("BSGS and primitive roots: all checks passed");
}
}
#include <cassert>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <set>
#include <unordered_map>
#include <vector>
using i64 = long long;
i64 pow_mod(i64 a, i64 e, i64 m) { // m < 2^31, so products fit in 64 bits
i64 r = 1;
a %= m;
for (; e > 0; e >>= 1, a = a * a % m)
if (e & 1) r = r * a % m;
return r;
}
// Smallest x >= 0 with g^x = h (mod prime p), or -1 if none.
i64 bsgs(i64 g, i64 h, i64 p) {
g %= p;
h %= p;
i64 m = (i64)std::sqrt((double)(p - 1)) + 1;
while (m * m <= p - 1) ++m;
std::unordered_map<i64, i64> table;
table.reserve(m * 2);
i64 cur = 1;
for (i64 j = 0; j < m; ++j) {
table.emplace(cur, j); // emplace keeps the first (smallest) j
cur = cur * g % p;
}
i64 giant = pow_mod(pow_mod(g, m, p), p - 2, p); // g^(-m) by Fermat
i64 gamma = h;
for (i64 i = 0; i < m; ++i) {
auto it = table.find(gamma);
if (it != table.end()) return i * m + it->second;
gamma = gamma * giant % p;
}
return -1;
}
std::vector<i64> prime_factors(i64 n) {
std::vector<i64> out;
for (i64 d = 2; d * d <= n; ++d)
if (n % d == 0) {
out.push_back(d);
while (n % d == 0) n /= d;
}
if (n > 1) out.push_back(n);
return out;
}
i64 primitive_root(i64 p) {
if (p == 2) return 1;
auto qs = prime_factors(p - 1);
for (i64 g = 2;; ++g) {
bool ok = true;
for (i64 q : qs)
if (pow_mod(g, (p - 1) / q, p) == 1) { ok = false; break; }
if (ok) return g;
}
}
int main() {
assert(bsgs(2, 22, 29) == 26);
assert(bsgs(3, 13, 17) == 4);
assert(bsgs(2, 3, 7) == -1);
assert(bsgs(5, 1, 23) == 0);
const i64 P = 1000000007;
assert(bsgs(5, pow_mod(5, 123456789, P), P) == 123456789);
for (i64 p : {7, 11, 13, 29, 101})
for (i64 g = 2; g < p; ++g)
for (i64 h = 1; h < p; ++h) {
i64 want = -1;
for (i64 x = 0; x < p - 1; ++x)
if (pow_mod(g, x, p) == h) { want = x; break; }
assert(bsgs(g, h, p) == want);
}
assert(primitive_root(7) == 3 && primitive_root(23) == 5);
assert(primitive_root(1000000007) == 5);
assert(primitive_root(998244353) == 3);
assert(primitive_root(1000000009) == 13);
std::set<i64> seen;
i64 g = primitive_root(101);
for (i64 k = 1; k <= 100; ++k) seen.insert(pow_mod(g, k, 101));
assert(seen.size() == 100);
std::cout << "BSGS and primitive roots: all checks passed\n";
}
// p < 2^31 but products reach 2^62 > 2^53, so multiply with BigInt.
const mulMod = (a: number, b: number, m: number): number =>
Number((BigInt(a) * BigInt(b)) % BigInt(m));
function powMod(a: number, e: number, m: number): number {
let r = 1;
a %= m;
for (; e > 0; e = Math.floor(e / 2), a = mulMod(a, a, m)) if (e % 2 === 1) r = mulMod(r, a, m);
return r;
}
/** Smallest x >= 0 with g^x = h (mod prime p), or -1 if none. */
function bsgs(g: number, h: number, p: number): number {
g %= p;
h %= p;
let m = Math.floor(Math.sqrt(p - 1)) + 1;
while (m * m <= p - 1) m++;
const table = new Map<number, number>();
let cur = 1;
for (let j = 0; j < m; j++) {
if (!table.has(cur)) table.set(cur, j);
cur = mulMod(cur, g, p);
}
const giant = powMod(powMod(g, m, p), p - 2, p); // g^(-m) by Fermat
let gamma = h;
for (let i = 0; i < m; i++) {
const j = table.get(gamma);
if (j !== undefined) return i * m + j;
gamma = mulMod(gamma, giant, p);
}
return -1;
}
function primeFactors(n: number): number[] {
const out: number[] = [];
for (let d = 2; d * d <= n; d++) {
if (n % d === 0) {
out.push(d);
while (n % d === 0) n /= d;
}
}
if (n > 1) out.push(n);
return out;
}
function primitiveRoot(p: number): number {
if (p === 2) return 1;
const qs = primeFactors(p - 1);
for (let g = 2; ; g++) if (qs.every((q) => powMod(g, (p - 1) / q, p) !== 1)) return g;
}
function assert(cond: boolean, msg: string): void { if (!cond) throw new Error(msg); }
assert(bsgs(2, 22, 29) === 26, "2^x=22 mod 29");
assert(bsgs(3, 13, 17) === 4, "3^x=13 mod 17");
assert(bsgs(2, 3, 7) === -1, "no solution");
assert(bsgs(5, 1, 23) === 0, "x = 0");
const P = 1_000_000_007;
assert(bsgs(5, powMod(5, 123_456_789, P), P) === 123_456_789, "big p");
for (const p of [7, 11, 13, 29, 101])
for (let g = 2; g < p; g++)
for (let h = 1; h < p; h++) {
let want = -1;
for (let x = 0; x < p - 1; x++) if (powMod(g, x, p) === h) { want = x; break; }
assert(bsgs(g, h, p) === want, `brute ${g} ${h} ${p}`);
}
assert(primitiveRoot(7) === 3 && primitiveRoot(23) === 5, "small roots");
assert(primitiveRoot(1_000_000_007) === 5, "1e9+7");
assert(primitiveRoot(998_244_353) === 3, "998244353");
assert(primitiveRoot(1_000_000_009) === 13, "1e9+9");
const seen = new Set<number>();
const g101 = primitiveRoot(101);
for (let k = 1; k <= 100; k++) seen.add(powMod(g101, k, 101));
assert(seen.size === 100, "generates everything");
console.log("BSGS and primitive roots: all checks passed");
Real-world uses
- RSA and DH key generation. OpenSSL's
BN_generate_prime_exdraws random odd candidates, sieves out small factors, then runs Miller–Rabin rounds. How many rounds is a policy decision guided by NIST's tables (FIPS 186-4, Appendix C.3, and its successor FIPS 186-5), which pick the count so the chance of accepting a composite is negligible (on the order of ) for the key size. - Language runtimes. Java's
BigInteger.isProbablePrime(certainty)runs Miller–Rabin rounds and, for numbers of 100 bits or more, adds a Lucas–Lehmer-style strong Lucas test (see the OpenJDK source ofBigInteger.primeToCertainty). Python'ssympy.isprimeuses deterministic Miller–Rabin below and Baillie–PSW above. - GMP, PARI/GP, Mathematica. GMP's
mpz_probab_prime_pdoes trial division, then Baillie–PSW (since GMP 6.2), then extra Miller–Rabin rounds. PARI'sispseudoprimeis Baillie–PSW;isprimeproduces a proof (APR-CL or ECPP). Gilchrist and Feitsma's exhaustive search confirmed there is no Baillie–PSW pseudoprime below . - Factoring records. Pollard's rho, in Brent's version, factored the eighth Fermat number (Brent and Pollard, 1981). Modern factoring of large numbers uses ECM and the number field sieve (RSA-250, 829 bits, factored in 2020 with about 2700 core-years), with rho still used for the small cofactors inside those algorithms.
- TLS and SSH parameter choice. Finite-field Diffie–Hellman groups (RFC 3526, RFC 7919) use safe primes to block Pohlig–Hellman. The Logjam paper (Adrian et al., ACM CCS 2015) is why 512-bit and shared 1024-bit DH groups were deprecated.
- NTT moduli. Number-theoretic transforms pick primes like and use a primitive root (3) to get roots of unity of order .
Pitfalls & edge cases
- Overflow in . Two 63-bit numbers multiply to 126 bits. In C++ use
unsigned __int128; in Java useBigIntegerorMath.multiplyHighwith a reduction; in JavaScript,Numberloses exactness above , so useBigInt. - Small and bases . Test divisibility by the base primes first, or reduce and skip .
- Even , , . Handle before the main loop; requires odd .
- Using 11 bases for 64-bit. fools bases . You need 37 too.
- Copying the "3.3 × 10²⁴" bound for 12 bases. That bound belongs to the 13 bases ; the 12 bases are proven only below . Both cover 64-bit, but don't extend the claim to 80-bit inputs.
- Pollard's rho on a prime or a prime power. On a prime it loops forever; always test primality first. Prime powers work (the cycle mod still collides), but some implementations special-case perfect powers for speed.
- Rho returning . Retry with a different ; do not return as a "factor".
- or . These cycle badly; use .
- Unseeded randomness in tests. Use a fixed seed or a deterministic sequence so failures reproduce.
- BSGS with or composite . The inverse does not exist; use the extended version.
- BSGS returning a non-minimal . If you overwrite table entries, a later (larger) wins. Keep the first.
- Forgetting that logs are modulo the order. If is a solution, so is . Problems that ask for "smallest positive" may want excluded.
- Primitive roots for composite moduli. They only exist for .
- Möbius sums with large . For , is , fine in 64-bit; at it overflows. Use 128-bit or a modulus.
Variations
- Strong Lucas and Baillie–PSW. Combine a base-2 strong test with a strong Lucas probable-prime test; the two kinds of pseudoprimes appear to be disjoint, and no counterexample is known.
- Pollard's method. Compute for ; if some prime has -smooth, reveals it. Same idea extended to elliptic curves gives ECM.
- Pollard's rho for logarithms and kangaroo (lambda) method. time with memory; kangaroo solves "log known to lie in an interval of width " in .
- Discrete root. Solve : with primitive root , find by BSGS, then solve (extended Euclid); all solutions are .
- Order of an element. Start with ; for each prime , while and , divide by .
- Counting primes up to . Legendre/Meissel–Lehmer/Lucy_Hedgehog methods use the same "only distinct values of " fact, in about or better.
- Sums of multiplicative functions. or for via Dirichlet convolution + divisor blocks + memoization (about ).
- Square-free counting. The number of square-free is .
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. Count Primes (LeetCode 204) — Count primes below . A warm-up that reminds you where the sieve stops being the right tool.
Hint
Sieve of Eratosthenes, starting crossing-out at . Miller–Rabin per number would also pass but is slower here: the sieve shares work.
2. Largest prime factor (Project Euler 3) — Largest prime factor of . Teaches the factorization loop.
Hint
Trial division suffices here (the factors are small). Run it through Pollard–Brent anyway and compare: .
3. Counting Divisors (CSES 1713) — For up to numbers , print the number of divisors. Teaches multiplicative functions from a smallest-prime-factor sieve.
Hint
Sieve the smallest prime factor; factor each query in and multiply .
4. Sum of Divisors (CSES 1082) — for . Teaches divisor blocks.
Solution
(each divides numbers). Group by ; a block contributes .
MOD = 10**9 + 7
def sum_of_divisors(n: int) -> int:
total, i = 0, 1
while i <= n:
q = n // i
j = n // q
block = (i + j) * (j - i + 1) // 2 # i + (i+1) + ... + j
total = (total + q % MOD * (block % MOD)) % MOD
i = j + 1
return total
assert sum_of_divisors(5) == 21 # 1 + 3 + 4 + 7 + 6
assert sum_of_divisors(10) == sum(sum(d for d in range(1, k + 1) if k % d == 0) for k in range(1, 11))
5. Primality Test (Library Checker) — Up to queries "is prime?". Teaches deterministic Miller–Rabin under a time limit.
Hint
The first code block of this lesson, in C++, with 128-bit products. Exit early on small-prime divisibility.
6. Factorize (Library Checker) — Factor up to 100 numbers . Teaches Pollard–Brent.
Solution
The second code block of this lesson. Key details: trial-divide tiny primes first, test primality before calling rho, use 128-bit mul_mod, batch gcds, and retry with a new on . In C++ the worst case (balanced semiprimes) runs in a few milliseconds per number.
7. Counting Coprime Pairs (CSES 2417) — Given numbers , count pairs with gcd 1. Teaches Möbius over divisors.
Solution
Let = how many input numbers are divisible by . Pairs with , the Möbius version of inclusion–exclusion over square-free .
def coprime_pairs_of(values: list[int]) -> int:
M = max(values)
cnt = [0] * (M + 1)
for v in values:
cnt[v] += 1
mu = [1] * (M + 1)
is_comp = [False] * (M + 1)
for p in range(2, M + 1):
if not is_comp[p]:
for k in range(p, M + 1, p):
if k > p:
is_comp[k] = True
mu[k] = -mu[k]
for k in range(p * p, M + 1, p * p):
mu[k] = 0
total = 0
for d in range(1, M + 1):
if mu[d]:
c = sum(cnt[d::d]) # numbers divisible by d
total += mu[d] * c * (c - 1) // 2
return total
assert coprime_pairs_of([5, 4, 20, 1, 16, 17, 5, 15]) == 19
8. Sum of gcd of Tuples (Hard) (AtCoder ABC 162 E) — Sum of over all tuples. Teaches "count tuples with gcd exactly " by subtracting multiples, the Möbius idea done by hand.
Hint
Let = tuples whose gcd is exactly . Tuples with all entries divisible by : . Go from down: .
9. Primitive Root (Library Checker) — Find a primitive root of a prime . Teaches factoring with Pollard's rho, then the test.
Hint
Random works well too: the fraction of primitive roots is , rarely below 0.2 in practice.
10. Discrete Logarithm (Library Checker) — Smallest with , where need not be prime. Teaches BSGS plus the extension for non-coprime moduli.
Solution
Strip common factors: while : if (and ) there is no solution; otherwise divide and by , multiply a running coefficient by , and add one to an offset; if at any point , return the offset. Then solve with by BSGS (store , or use the variant that needs no inverse), and add the offset. Remember to check small first. cp-algorithms "Discrete Logarithm" walks through it.
11. Lunar New Year and a Recursive Sequence (Codeforces 1106F) — A sequence is defined by multiplying powers of earlier terms modulo 998244353; recover a starting value. Teaches the full pipeline: primitive root 3, logs turn products into sums, matrix exponentiation on exponents modulo , BSGS, then a linear congruence.
Hint
Write every term as . The exponents follow a linear recurrence modulo ; compute the coefficient of the unknown with Matrix Exponentiation. Then of the given value by BSGS, and solve .
12. Relatively Prime Powers (Codeforces 1036F) — Count numbers up to that are not perfect powers in disguise (exponent gcd 1). Teaches Möbius over exponents and careful integer -th roots.
Hint
Count of numbers that are perfect -th powers is about . The answer is , up to 60. Fix floating-point roots by adjusting ±1.
Common mistakes & interview follow-ups
"Why not just use Fermat's test?" Carmichael numbers: 561 passes for all 320 coprime bases. Explain the square-root-of-1 strengthening and the bound.
"Is Miller–Rabin deterministic?" It is randomized in general (error ), but for 64-bit inputs the fixed 12 bases make it a proof. Under GRH, testing all bases is deterministic for every (Bach, 1990).
"Why is rho ?" Birthday paradox modulo the unknown smallest prime : a collision after about steps. Note it is a heuristic.
"Floyd vs Brent?" Floyd: three function evaluations per step, simple. Brent: one evaluation per step, tortoise teleports at powers of two. Both ; Brent is faster in practice.
"What if two primes are found in the same batch?" The gcd becomes ; replay the batch step by step, and if still , change .
"Why is the discrete log hard, and how is that used?" Only generic attacks exist in well-chosen groups (Shoup's bound for generic algorithms), and sub-exponential ones for ; DH and DSA security rest on it. Mention Pohlig–Hellman and why safe primes matter.
"BSGS uses memory. Can you avoid that?" Pollard's rho for logs (or kangaroo) with memory, same expected time.
Mistakes interviewers watch for: 64-bit overflow in mulmod; forgetting n - 1 = 2^s d must have odd; looping the squaring times instead of (harmless but sloppy); calling rho on a prime; BSGS with too small to cover the period; using floating sqrt without correcting.
Quick quiz
1. , . The Miller–Rabin chain is . Which value proves 561 composite, and what factor does it reveal?
Answer
67: it squares to 1 but is not . and .
2. Why do the 11 bases not suffice for 64-bit integers?
Answer
is composite and is a strong probable prime to all of them. Base 37 exposes it.
3. Floyd's rho on with , finds 97 at step 3. Why 97 and not 83?
Answer
Modulo 97 the sequence enters a 3-cycle after one step, so tortoise and hare meet modulo 97 at step 3. Modulo 83 the tail is 4 and the cycle is 5, so they have not met yet.
4. In BSGS for , why is enough?
Answer
Exponents only matter modulo , and with covers .
5. Why is a terrible prime for Diffie–Hellman even if it were 2048 bits long with the same shape?
Answer
would be smooth (mostly powers of 2), so Pohlig–Hellman reduces the log to tiny subgroups. DH needs to have a large prime factor (safe primes).
6. How many distinct values does take for , roughly?
Answer
About . That is why the block loop is fast.
Further reading / sources
- Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, 2nd ed. (2005) — §3.5 (Miller–Rabin and the bound), §5.2 (Pollard rho), §5.3 (discrete logs, BSGS, Pohlig–Hellman), §6 (index calculus, NFS).
- Donald E. Knuth, The Art of Computer Programming, Vol. 2, 3rd ed. — §4.5.4 (factoring and primality; analysis of rho), Ex. 3.1-6 (cycle detection).
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed. — §31.8 (primality testing, Miller–Rabin), §31.9 (Pollard's rho).
- Michael O. Rabin, "Probabilistic algorithm for testing primality", Journal of Number Theory 12(1), 1980; Louis Monier, "Evaluation and comparison of two efficient probabilistic primality testing algorithms", Theoretical Computer Science 12(1), 1980.
- Gary L. Miller, "Riemann's Hypothesis and Tests for Primality", JCSS 13(3), 1976.
- Carl Pomerance, John L. Selfridge, Samuel S. Wagstaff Jr., "The pseudoprimes to ", Mathematics of Computation 35(151), 1980.
- Gerhard Jaeschke, "On strong pseudoprimes to several bases", Mathematics of Computation 61(204), 1993.
- Yupeng Jiang and Yingpu Deng, "Strong pseudoprimes to the first eight prime bases", Mathematics of Computation 83(290), 2014; Jonathan Sorenson and Jonathan Webster, "Strong pseudoprimes to twelve prime bases", Mathematics of Computation 86(304), 2017.
- W. R. Alford, Andrew Granville, Carl Pomerance, "There are infinitely many Carmichael numbers", Annals of Mathematics 139(3), 1994.
- J. M. Pollard, "A Monte Carlo method for factorization", BIT 15, 1975; Richard P. Brent, "An improved Monte Carlo factorization algorithm", BIT 20, 1980; R. P. Brent and J. M. Pollard, "Factorization of the eighth Fermat number", Mathematics of Computation 36(154), 1981.
- Daniel Shanks, "Class number, a theory of factorization, and genera", Proc. Symp. Pure Math. 20, 1971 (baby-step giant-step); Stephen Pohlig and Martin Hellman, "An improved algorithm for computing logarithms over GF(p)", IEEE Trans. Inf. Theory 24(1), 1978.
- Victor Shoup, "Lower bounds for discrete logarithms and related problems", EUROCRYPT 1997.
- Whitfield Diffie and Martin Hellman, "New directions in cryptography", IEEE Trans. Inf. Theory 22(6), 1976.
- David Adrian et al., "Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice", ACM CCS 2015 (Logjam).
- RFC 3526 and RFC 7919 (finite-field DH groups); NIST FIPS 186-4 (2013), Appendix C.3 (probabilistic primality tests), superseded by FIPS 186-5 (2023).
- cp-algorithms: Primality tests, Integer factorization, Discrete logarithm, Primitive root, Euler's totient function.
- OEIS: A002997 Carmichael numbers, A014233 smallest strong pseudoprimes to the first prime bases, A008683 Möbius function.
Lessons: previous — Modular Arithmetic · next — Combinatorics · module — Mathematics for Algorithms · course — DSA: Zero to Mastery.
Related Archon pages: Number Theory Basics · Randomized Algorithms · String Hashing · Hash Tables · Matrix Exponentiation · Counting & Combinatorial DP · Bit Manipulation · Cryptography for Engineers · Practical Cryptography · FFT & NTT · Cryptography in the Real World.