Overview

A polynomial ring is a set of polynomials where polynomial computations over the

(+,⋅)

operators (e.g.,

f_{1} + f_{2}

f_{1} \cdot (f_{2} - f_{3})

f_{1} + f_{2} + f_{4}

) are closed, associative, commutative, and distributive.

A polynomial ring

ℤ_{q} [x] ∕ (x^{n} + 1)

is the set of all polynomials

f_{i}

that have the following properties:

$⟨$ Summary A-5.1 $⟩$ Ring

For a polynomial $f \in ℤ_{q} [x] ∕ (x^{n} + 1)$ where $f = c_{0} + c_{1} x^{1} + \dots + c_{n - 1} x^{n - 1}$ :

Coefficient Ring: $f_{i}$ ’s each polynomial coefficient $c_{j}$ is in integer modulo $p$ .
(i.e., $c_{i} + q \equiv c_{i} mod q$ ).
Degree Ring: Any polynomial $f^{'}$ can be broken down to:

$f^{'} = (x^{n} + 1) (f_{q}) + f_{r} \equiv f_{r} \in ℤ_{q} [x] ∕ (x^{n} + 1)$

, where $f_{q}$ is called a quotient polynomial and $f_{r}$ is called a remainder polynomial resulting from the polynomial division of $f^{'}$ divided by $x^{n} + 1$ .
Polynomial Congruence: If two polynomials are congruent, they belong to the same equivalence class, in which case they are interchangeable in the polynomial operations ( $+,⋅$ ) in the polynomial ring. For example, if:
$f^{'} \equiv f_{r 1} \in ℤ_{q} [x] ∕ (x^{n} + 1)$
$f^{″} \equiv f_{r 2} \in ℤ_{q} [x] ∕ (x^{n} + 1)$
$f_{r 1} + f_{r 2} \equiv f_{r 3} \in ℤ_{q} [x] ∕ (x^{n} + 1)$

, then the polynomial operation result of $f^{'} + f^{″}$ is in the same equivalence class as:
$f^{'} + f^{″} \equiv f_{r 1} + f_{r 2} \equiv f_{r 3} \in ℤ_{q} [x] ∕ (x^{n} + 1)$

To make the notation simple, we denote the polynomial ring $ℤ_{q} [x] ∕ (x^{n} + 1)$ as $R_{⟨ n, q ⟩}$

Recall that in a ring

ℤ_{p}

, a big number

b

can be divided by

p

and

b = q \cdot p + r \equiv r mod p

(the quotient

q

gets eliminated). Similarly, in a polynomial ring

R_{⟨ n, q ⟩}

, a high-degree polynomial

f_{𝑏𝑖𝑔}

can be divided by a polynomial modulo

x^{n} + 1

, which gives:

f_{𝑏𝑖𝑔} = (X^{n} + 1) \cdot (f_{q}) + f_{r} \equiv f_{r} \in R_{⟨ n, q ⟩}

, whereas

f_{q}

is a quotient polynomial and

f_{r}

is a remainder polynomial. In this case,

f_{𝑏𝑖𝑔}

is congruent to (i.e., is in the same equivalence class as)

f_{r}

. Thus,

f_{q}

can be eliminated and

f_{r}

(i.e., the simplified version of

f_{𝑏𝑖𝑔}

) can be interchangeably used for polynomial operations

(+,⋅)

in the polynomial ring. Polynomial simplification in a polynomial ring is done by substituting

x^{n} \equiv - 1

into

f_{𝑏𝑖𝑔}

, because

x^{n} + 1 \equiv 0

in the polynomial ring (this is the same as the case of a number ring modulo

p

where

p \equiv 0

). This way, a high-degree polynomial

f_{𝑏𝑖𝑔}

can be recursively simplified to a polynomial of degree less than

n

by recursively substituting

x^{n} \equiv - 1

into

f_{𝑏𝑖𝑔}

For a polynomial modulo, we normally choose a cyclotomic polynomial

x^{n} + 1

(where

n

2^{p}

for some integer

p

) as the divisor, as it provides computational efficiency.

A-5.1.1 Example

Given

f \in ℤ_{7} [x] ∕ (x^{2} + 1)

, suppose

f = x^{4} + 3 x^{3} + 11 x^{2} + 6 x + 10

. Then,

Thus,

f (x) = x^{4} + 3 x^{3} + 11 x^{2} + 6 x + 10

is equivalent to (

\equiv

)

3 x

in the polynomial ring

ℤ_{7} [x] ∕ (x^{2} + 1)

A-5.1.2 Discussion


	Ring	Polynomial Ring


Set Elements	number	polynomial

Ring Notation	$ℤ_{p} = {0, 1, \dots, p - 1}$	$ℤ_{p} [x] ∕ (x^{n} + 1)$
& Definition	The set of all integers between $0$ and $p$	The set of all polynomials $f$ such that
		$f = c_{0} + c_{1} x^{1} + c_{2} x^{2} \dots + c_{n - 1} x^{n - 1}$
		where each coefficient $c_{i} \in ℤ_{p}$
		and $f$ ’s degree is less than $n$

Supported	$(+,⋅)$	$(+,⋅)$
Operations	(Addition, Multiplication)	(Addition, Multiplication)

( $+$ ) Operation	We know how to add numbers	$f_{a} = a_{0} + a_{1} x^{1} + a_{2} x^{2} \dots + a_{d_{a} - 1} x^{d_{a} - 1}$
		$f_{b} = b_{0} + b_{1} x^{1} + b_{2} x^{2} \dots + b_{d_{b} - 1} x^{d_{b} - 1}$
		Then, $f_{a} + f_{b}$ is computed as:
		$f_{c} = \sum_{i = 0}^{𝗆𝖺𝗑 (d_{a}, d_{b})} (a_{i} + b_{i}) x^{i}$

( $\cdot$ ) Operation	We know how to multiply numbers	$f_{a} = a_{0} + a_{1} x^{1} + a_{2} x^{2} \dots + a_{d_{a} - 1} x^{d_{a} - 1}$
		$f_{b} = b_{0} + b_{1} x^{1} + b_{2} x^{2} \dots + b_{d_{b} - 1} x^{d_{b} - 1}$
		Then, $f_{a} \cdot f_{b}$ is computed as:
		$f_{c} = \sum_{i = 0}^{d_{a} + d_{b}} ∑_{j = 0}^{i} a_{j} b_{i - j} x^{i}$

	For $a, b \in ℤ_{p}$	For $f_{a}, f_{b} \in ℤ_{p} [X] ∕ (x^{x} + 1)$ ,
Commutative	$a + b = b + a$	$f_{a} + f_{b} = f_{b} + f_{a}$
Associative	$(a + b) + c = a + (b + c)$	$(f_{a} + f_{b}) + f_{c} = f_{a} + (f_{b} + f_{c})$
Distributive	$a \cdot (b + c) = a \cdot b + a \cdot c$	$f_{a} \cdot (f_{b} + f_{c}) = f_{a} \cdot f_{b} + f_{a} \cdot f_{c}$
Closed	$a + b \equiv c \in ℤ_{p}$ , $a \cdot b \equiv d \in ℤ_{p}$	$f_{a} + f_{b} \equiv f_{c} \in R_{⟨ n, q ⟩}$ ,
		$f_{a} \cdot f_{b} \equiv f_{d} \in R_{⟨ n, q ⟩}$

Congruency ( $\equiv$ )	Two numbers $a \equiv b$ in modulo $p$ if:	Two polynomials $f_{a} \equiv f_{b}$ in $ℤ_{p} [x] ∕ (x^{n} + 1)$ if:
	$(a mod p) = (b mod p)$	$f_{a}^{'} = f_{a} mod (x^{n} + 1) = \sum_{i = 0}^{d_{a}} a_{i} x^{i}$
		$f_{b}^{'} = f_{b} mod (x^{n} + 1) = \sum_{i = 0}^{d_{b}} b_{i} x^{i}$ ,
		$d_{a} = d_{b}$ and $a_{i} \equiv b_{i}$ in modulo $p$
		for all $0 \leq i \leq d_{a}$

Table 1: Comparison between a number ring and a polynomial ring.

Congruency: If two numbers are congruent, they are in the same congruency class. The same is true for two congruent polynomials. If the computation results of two mathematical formulas belong to the same congruency class, then their computations wrap around within modulo of their congruency. This is a useful property for cryptographic schemes where encryption & decryption computations wrap around their values within a limited set of binary bits. Congruency is useful for simplifying computation. For example, a big number or a complex polynomial can be normalized to a simpler number or polynomial by using the congruency rule, which reduces the computation overhead.

Polynomial Evaluation: Note that two numbers that belong to the same congruency class are not necessarily the same number. For example,

5 \equiv 10

modulo 5, but these two numbers are not the same. Likewise, two congruent polynomials are not the same. While two congruent polynomials in a polynomial ring can be interchangeably used for polynomial operations supported in the ring (i.e.,

(+,⋅)

), such as

f_{1} + f_{2}

f_{1} \cdot (f_{2} - f_{3})

, two congruent polynomials do not necessarily give the same result when they are evaluated for a certain variable value

x = a

. For example, in the previous example of §A-5.1.1, the two polynomials

x^{4} + 3 x^{3} + 11 x^{2} + 6 x + 10

and

3 x

are congruent in the polynomial ring

ℤ_{7} [x] ∕ (x^{2} + 1)

. However, these two polynomials do not give the same evaluation results for

x = 0

: the original polynomial gives 10, whereas the reduced (i.e., simplified) polynomial gives 0. This discrepency in evaluation occurs because we defined two polynomials

M_{1}

and

M_{2}

to be congruent over

x^{n} + 1

(i.e.,

M_{1} \equiv M_{2}

) if their remainder is the same after being divided by

X^{n} + 1

(i.e.,

M_{1} = Q \cdot (X^{n} + 1) + M_{2}

for some polynomial

Q

). Therefore,

M_{1}

and

M_{2}

will be evaluated to the same polynomial

M_{2}

if they are evaluated at the

x

values such that

X^{n} = - 1

, which make the

X^{n} + 1

term 0. The solutions for

x^{n} = - 1

are called the

n

-th roots of unity, which we will learn in §A-7 and §A-9. We summarize as follows:

$⟨$ Summary A-5.1.2 $⟩$ Polynomial Evaluation over Polynomial Ring

Suppose polynomials $M_{1}$ and $M_{2}$ are congruent over the polynomial ring $x^{n} + 1$ . This is equivalent to the following relation: $M_{1} = Q \cdot (X^{n} + 1) + M_{2}$ $Q$ for some polynomial $Q$ . Then, $M_{1} (X)$ and $M_{2} (X)$ are guaranteed to be evaluated to the same value if $X = x_{i}$ is the solution for $X^{n} + 1$ (i.e., $X$ is the $n$ -th root of unity). That is , $M_{1} (x_{i}) = M_{2} (x_{i})$ .

Number Ring & Polynomial Ring: These two rings share many common characteristics, which are summarized in Table 1.

A-5.1 Overview

A-5.1.1 Example

A-5.1.2 Discussion