# 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$