Cyclotomic polynomial

✍️ → Written on 2020-07-17 in 557 words. Part of cs IT-security pqcrypto

In post-quantum cryptography and fully homomorphic encryption, the quotient ring (ℤ_q[x])/(x^n + 1) is recurring. But why is the reduction polynomial x^n + 1? What is the reason?

The answer is that it is a cyclotomic polynomial with a desirable property for the Number Theoretic Transform (to speed up polynomial multiplication).

Preliminaries

gcd

greatest common divisor of two (can be pairwise generalized to an arbitrary number of arguments) positive numbers is the largest value dividing all arguments. Must be 1 or any larger integer. Often evaluated with the Euclidean algorithm.

coprime

two numbers are coprime if their gcd is 1

polynomial

a formal expression $\sum_{i=0}^\infty a_i x^i$ in one indeterminate $x$ over a ring (or field) $R$ where $a_i$ are called coefficients. Abstract algebra distinguishes it from polynomial functions which can actually evaluate to a value by substitution.

monic polynomial

a polynomial with the leading coefficient 1 (i.e. $a_k = 1$ with $a_i = 0$ for any $i > k$)

Just like integers, polynomials can be factorized. $(6x^2 + 4x) = (2x)·(3x + 2)$. Hence polynomial $(6x^2 + 4x)$ can be factored into polynomials $(2x)$ and $(3x + 2)$.

irreducible polynomial

A polynomial that cannot be factored into two non-constant polynomials. The definition of factorization depends on the underlying ring (or field) of the polynomial. $(x^2 + 1)$ is irreducible in ℝ, but not reducible in ℂ.

n-th roots of unity (= de Moivre number)

satisfies $z^n = 1$ for $n \in \mathbb Z_{\geq 1}$

primitive n-th roots of unity

a n-th root of unity which is not an m-th root of unity for any $m < n$

Complex redux

Basic properties of complex numbers:

• $e^{ix} = \cos{x} + i\sin{x}$ (Euler’s formula)

• $e^{i\pi} + 1 = 0$ (Euler’s identity, special case of Euler’s formula with x = π)

• $e^{0\pi i} = e^{2\pi i} = 1$, $e^{\frac\pi2 i} = i$, $e^{\pi i} = -1$, $e^{\frac32\pi i} = -i$

Definition

Let n be any positive integer n. The following definitions of the n-th cyclotomic polynomial are given on Wikipedia:

• The unique irreducible polynomial with integer coefficients that is a divisor of $x^n - 1$ and is not a divisor of $x^k - 1$ for any $k < n$. The irreducible polynomial’s roots are all n-th primitive roots of unity $e^{2i\pi \frac{k}{n}}$, where $k$ runs over the positive integers not greater than n and coprime to n.

• $\Phi_n(x) = \prod_{gcd(k,n)=1 ; 1 \leq k \leq n} \left(x - e^{2i\pi \frac{k}{n}}\right)$.

• Monic polynomial with integer coefficients that is the minimal polynomial over the field of the rational numbers of any primitive n-th root of unity.

Now since most algorithms pick $n$ as power of 2, these values are especially interesting and share some structure:

$\Phi_n(x) = x^{\frac n2} + 1$