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: