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 ${\displaystyle P}$ of prime numbers, the Swinnerton-Dyer polynomial associated to ${\displaystyle P}$ is the polynomial: $${\displaystyle f_{P}(x)=\prod \left(x+\sum _{p\in P}(\pm ){\sqrt {p}}\right)}$$ where the product extends over all ${\displaystyle 2^{|P|}}$ choices of sign in the enclosed sum. The polynomial ${\displaystyle f_{P}(x)}$ has degree ${\displaystyle 2^{|P|}}$ and integer coefficients, which alternate in sign. If ${\displaystyle |P|>1}$, then ${\displaystyle f_{P}(x)}$ is reducible modulo ${\displaystyle p}$ for all primes ${\displaystyle p}$, into linear and quadratic factors, but irreducible over ${\displaystyle \mathbb {Q} }$. The Galois group of ${\displaystyle f_{P}(x)}$ is ${\displaystyle \mathbb {Z} _{2}^{|P|}}$.

The first few Swinnerton-Dyer polynomials are: $${\displaystyle f_{\{2\}}(x)=x^{2}-2=(x-{\sqrt {2}})(x+{\sqrt {2}})}$$ $${\displaystyle f_{\{2,3\}}(x)=x^{4}-10x^{2}+1=(x-{\sqrt {2}}-{\sqrt {3}})(x-{\sqrt {2}}+{\sqrt {3}})(x+{\sqrt {2}}-{\sqrt {3}})(x+{\sqrt {2}}+{\sqrt {3}})}$$ $${\displaystyle f_{\{2,3,5\}}(x)=x^{8}-40x^{6}+352x^{4}-960x^{2}+576.}$$

• von zur Gathen, Joachim; Gerhard, Jürgen (April 2013). Modern Computer Algebra (Third ed.). Cambridge University Press. ISBN 9781107039032.
• Vardi, I (1991), Computational Recreations in Mathematica, Addison-Wesley, pp. 225–226
• Weisstein, Eric W. "Swinnerton-Dyer polynomial". MathWorld.
• OEIS: A153731