Swinnerton-Dyer polynomial
In algebra, the Swinnerton-Dyer polynomials are a family of polynomials, introduced by Peter Swinnerton-Dyer, that serve as examples where polynomial factorization algorithms have worst-case runtime. They have the property of being reducible modulo every prime, while being irreducible over the rational numbers. They are a standard counterexample in number theory.
Given a finite set of prime numbers, the Swinnerton-Dyer polynomial associated to is the polynomial:
where the product extends over all choices of sign in the enclosed sum. The polynomial has degree and integer coefficients, which alternate in sign. If, then is reducible modulo for all primes, into linear and quadratic factors, but irreducible over. The Galois group of is.
The first few Swinnerton-Dyer polynomials are: