Swinnerton-Dyer polynomial

The Swinnerton-Dyer polynomials are a family of irreducible integer polynomials that split into many small factors modulo every prime^[1]. For the first $k$ primes $p_1,\dots ,p_k$, ${\mathrm{SD}}_k$ is the product of $x-(\pm \sqrt{p_1}\pm \cdots \pm \sqrt{p_k})$ over all $2^k$ choices of signs; expanding it leaves integer coefficients. The polynomial is irreducible over $\mathbb{Q}$, yet modulo any prime it factors into linear and quadratic factors only. Factoring over the integers by Hensel lifting relies on modular factorizations that resemble the true one; for these polynomials no prime gives such a hint, and the recombination step must try exponentially many combinations of modular factors. Knuth attributes the example to Peter Swinnerton-Dyer^[1], and it became the standard illustration of why the Berlekamp–Zassenhaus algorithm is exponential in the worst case and why lattice reduction was brought into factoring^[4][5].

The polynomial can be built one square root at a time. If $P$ is the polynomial for the first $k-1$ primes, then $P(x+\sqrt{p})P(x-\sqrt{p})$ is the next; writing $P(x+\sqrt{p})=u(x)+v(x)\sqrt{p}$ with integer polynomials $u$ and $v$, the product is $u^2-p{v}^2$. The degree doubles with each prime.

open Zpoly
 
(* SD_k(x) = product over all signs of (x - sum ± sqrt(p_i)), built one
   square root at a time: P(x + s) P(x - s) = u^2 - p v^2 where
   P(x + s) = u + v s in Z[x][s]/(s^2 - p). *)
let adjoin p (f : t) =
  let pz = Z.of_int p in
  (* Horner's rule with x + s, on pairs (u, v) meaning u + v s *)
  let u, v = Array.fold_right (fun c (u, v) ->
      (* (u + v s)(x + s) + c = (x u + p v + c) + (u + x v) s *)
      (add (add (shift u 1) (scale v pz)) (const c), add u (shift v 1))) f ([||], [||]) in
  sub (mul u u) (scale (mul v v) pz)
 
let primes = [ 2; 3; 5; 7; 11; 13 ]
let swinnerton_dyer k = List.fold_left (fun f p -> adjoin p f) x (List.filteri (fun i _ -> i < k) primes)

open Zpoly

SD_1 = x^2 - 2
SD_2 = x^4 - 10x^2 + 1
SD_3 = x^8 - 40x^6 + 352x^4 - 960x^2 + 576
SD_4: degree 16, largest coefficient 13950764
SD_5: degree 32, largest coefficient 255690851718529024

The roots of ${\mathrm{SD}}_k$ are the numbers $\pm \sqrt{p_1}\pm \cdots \pm \sqrt{p_k}$, and each of them generates the field $\mathbb{Q}(\sqrt{p_1},\dots ,\sqrt{p_k})$, which has degree $2^k$ over $\mathbb{Q}$ because square roots of distinct primes are linearly independent over the rationals^[8]. A root therefore has a minimal polynomial of degree $2^k$, which must be ${\mathrm{SD}}_k$ itself. The Galois group of this field is $(\mathbb{Z}/2{)}^k$, each element flipping the signs of some of the square roots.

Modulo a prime $q$ not dividing the discriminant, the degrees of the irreducible factors of a polynomial are the cycle lengths of the Frobenius element of $q$ acting on its roots. Every element of $(\mathbb{Z}/2{)}^k$ has order 1 or 2, so every cycle has length 1 or 2, and every factor modulo $q$ has degree at most 2^[2]. More concretely: ${\mathbb{F}}_{q^2}$ contains a square root of every element of ${\mathbb{F}}_q$, so all roots of ${\mathrm{SD}}_k$ modulo $q$ lie in ${\mathbb{F}}_{q^2}$.

(* Degrees of the factors of SD_4, of degree 16, modulo the odd primes
   below 60 that do not divide its discriminant. *)

mod 11: 2 2 2 2 2 2 2 2
mod 13: 2 2 2 2 2 2 2 2
mod 17: 2 2 2 2 2 2 2 2
mod 19: 2 2 2 2 2 2 2 2
mod 23: 2 2 2 2 2 2 2 2
mod 29: 2 2 2 2 2 2 2 2
mod 31: 2 2 2 2 2 2 2 2
mod 37: 2 2 2 2 2 2 2 2
mod 41: 2 2 2 2 2 2 2 2
mod 47: 2 2 2 2 2 2 2 2
mod 53: 2 2 2 2 2 2 2 2

The Berlekamp–Zassenhaus algorithm factors modulo a prime, lifts, and tests subsets of the lifted factors for divisibility over the integers^[7][1]. For an irreducible polynomial with $r$ modular factors, it tests subsets of up to half the factors before concluding that no proper subset gives a factor, some $2^{r-1}$ of them. For ${\mathrm{SD}}_k$, $r\ge 2^{k-1}$ for every prime, so the number of tests is doubly exponential in $k$ and exponential in the degree.

(* Zassenhaus's algorithm on SD_k: the number of modular factors and of
   subsets tried before the polynomial is found to be irreducible. *)

k  degree  prime  modular factors  subsets tried  factors over Z
2       4      5                2              2               1
3       8      7                4             10               1
4      16     11                8            162               1
5      32     19               16          39202               1

Kaltofen, Musser and Saunders generalized the construction to a wider class of polynomials that are hard for this approach^[6]. Choosing the prime cleverly, or combining information from several primes, does not help, since every prime gives the same picture.

Lenstra, Lenstra and Lovász showed in 1982 that polynomials over the rationals can be factored in polynomial time, using lattice basis reduction to find a factor from a single modular factor lifted to high precision^[4]. Their algorithm was slower than Berlekamp–Zassenhaus on typical inputs. Van Hoeij's algorithm of 2002 applies lattice reduction to the recombination problem itself, as a knapsack over traces of the modular factors, and handles Swinnerton-Dyer polynomials of high degree quickly; it is the method used in current computer algebra systems^[5].

Knuth's The Art of Computer Programming presents the polynomials, crediting Swinnerton-Dyer, as an example that defeats the heuristic of factoring modulo several primes and comparing the degrees of the factors^[1]. The simplest polynomial with the same behaviour, $x^4+1$, whose Galois group is also $(\mathbb{Z}/2{)}^2$, had long been known to be irreducible over the integers and reducible modulo every prime^[3]. Kaltofen, Musser and Saunders studied hard-to-factor classes in 1983^[6], the LLL algorithm of 1982 made factoring polynomial in theory^[4], and van Hoeij's 2002 algorithm made it fast in practice^[5].

• Hensel liftingHensel lifting turns a factorization of a polynomial modulo a prime p into a factorization modulo p², p⁴ and so on, as long as the factors modulo p are coprime. Each step solves a linear equation using the Bézout relation between the factors, and in quadratic form it doubles the precision, the p-adic analogue of Newton's method. It is the core of Zassenhaus's algorithm for factoring integer polynomials: factor modulo a small prime, lift until the modulus exceeds twice the Landau–Mignotte bound, and recombine the lifted factors into true factors over the integers.
• Cantor–Zassenhaus algorithmThe Cantor–Zassenhaus algorithm is a randomized method for factoring polynomials over a finite field. After the input is made square-free, distinct-degree factorization separates the irreducible factors by degree, using the fact that x^(p^d) − x is the product of all monic irreducibles whose degree divides d. Each group, a product of factors of the same degree d, is then split by taking the gcd with a^((p^d − 1)/2) − 1 for a random polynomial a: by the Chinese remainder theorem, this power is +1 or −1 independently in each factor's field, so the gcd separates the factors with probability about one half. It runs in expected polynomial time and is the standard method in computer algebra systems.
• Landau–Mignotte boundThe Landau–Mignotte bound limits the coefficients of any factor of an integer polynomial in terms of the polynomial itself: if g of degree k divides f, then each coefficient of g is at most binom(k, j) times the Euclidean norm of f, up to the ratio of leading coefficients, so all are below 2^k ‖f‖₂. It follows from Landau's inequality for the Mahler measure. Computer algebra algorithms use it to decide how large a modulus is needed to recover a factor or a gcd from its image modulo a prime power or a product of primes, as in Hensel lifting and the modular gcd. Factors can have larger coefficients than the polynomial they divide, so some such bound is necessary.
• Berlekamp's algorithmBerlekamp's algorithm factors a square-free polynomial f over a finite field F_p by linear algebra. The polynomials v with v^p = v modulo f form a vector space whose dimension is exactly the number r of irreducible factors of f; it is the null space of Q - I, where Q is the matrix of the Frobenius map v -> v^p. Any nonconstant v in it splits f as the product of gcd(f, v - s) over s in F_p. For large p a random element of the space and one exponentiation split f with probability about one half.

• Building a CAS in OCaml Part 4Factorization over Z by way of a finite field: Cantor-Zassenhaus, Berlekamp, Hensel lifting and subset recombination, then rational functions and partial fractions on top.

1. [1]D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, §4.6.2, Addison-Wesley (3rd ed., 1997).
2. [2]J. von zur Gathen, J. Gerhard, Modern Computer Algebra, §15.3, Cambridge University Press (3rd ed., 2013).
3. [3]E. R. Berlekamp, “Factoring polynomials over large finite fields”, Mathematics of Computation 24 (1970).
4. [4]A. K. Lenstra, H. W. Lenstra, L. Lovász, “Factoring polynomials with rational coefficients”, Mathematische Annalen 261 (1982).
5. [5]M. van Hoeij, “Factoring polynomials and the knapsack problem”, Journal of Number Theory 95 (2002).
6. [6]E. Kaltofen, D. R. Musser, B. D. Saunders, “A generalized class of polynomials that are hard to factor”, SIAM Journal on Computing 12 (1983).
7. [7]H. Zassenhaus, “On Hensel factorization, I”, Journal of Number Theory 1 (1969).
8. [8]A. S. Besicovitch, “On the linear independence of fractional powers of integers”, Journal of the London Mathematical Society 15 (1940).

last updated 28 September 2026