Coefficient Rotation

A-5.2 Coefficient Rotation

Coefficient rotation is a process of shifting the entire coefficients of a polynomial (either to the left or right) in a polynomial ring. In order to rotate the entire coefficients of a polynomial by $h$ positions to the left, we multiply $x^{- h}$ to the polynomial.

For example, suppose we have a polynomial as follows:

$f (x) = c_{0} + c_{1} x^{1} + c_{2} x^{2} + \dots + c_{h} x^{h} + \dots + c_{n - 1} x^{n - 1} \in R_{⟨ n, q ⟩}$

To shift the entire coefficients of $f$ to the left by $h$ positions (i.e., shift $f$ ’s $h$ -th coefficient to the constant term), we compute $f \cdot x^{- h}$ , which is:

$⟨$ Summary A-5.2 $⟩$ Polynomial Rotation

Give the $(n - 1)$ -degree polynomial:

$f (x) = c_{0} + c_{1} x^{1} + c_{2} x^{2} + \dots + c_{h} x^{h} + \dots + c_{n - 1} x^{n - 1} \in R_{⟨ n, q ⟩}$

The coefficients of $f (x)$ can be rotated to the left by $h$ positions by multiplying to $f (x)$ by $x^{- h}$ as follows:

$f (x) \cdot x^{- h} = c_{0} \cdot x^{- h} + c_{1} x^{1} \cdot x^{- h} + c_{2} x^{2} \cdot x^{- h} + \dots + c_{h} x^{h} \cdot x^{- h} + \dots + c_{n - 1} x^{n - 1} \cdot x^{- h}$ $\equiv c_{h} + c_{h + 1} x + c_{h + 2} x^{2} + \dots + c_{n - 1} x^{n - 1 - h} - c_{0} x^{n - h} - \dots - c_{h - 1} x^{n - 1} \in R_{⟨ n, q ⟩}$

Note that multiplying the two polynomials $f$ and $x^{- h}$ will have a congruent polynomial in $R_{⟨ n, q ⟩}$ . Therefore, the rotated polynomial, which is the result of $f \cdot x^{- h}$ , will also have a congruent polynomial in $R_{⟨ n, q ⟩}$ .

Note that the coefficient signs change when they rotate around the boundary of $x^{n} (= - 1)$ , as the computation is done in the polynomial ring $Z_{q} [x] ∕ (x^{n} + 1)$ .

A-5.2.1 Example

Suppose we have a polynomial $f \in ℤ_{8} ∕ (x^{4} + 1)$ as follows:

$ℤ_{8} = {- 4, - 3, - 2, - 1, 0, 1, 2, 3}$

$f = 2 + 3 x - 4 x^{2} - x^{3}$

The polynomial ring $ℤ_{8} ∕ (x^{4} + 1)$ has the following 4 congruence relationships:

$x^{4} \equiv - 1$

$x^{4} \cdot x^{- 1} \equiv - 1 \cdot x^{- 1}$

$x^{3} \equiv - x^{- 1}$

$x^{4} \equiv - 1$

$x^{4} \cdot x^{- 3} \equiv - 1 \cdot x^{- 3}$

$x \equiv - x^{- 3}$

$x^{4} \equiv - 1$

$x^{4} \cdot x^{- 2} \equiv - 1 \cdot x^{- 2}$

$x^{2} \equiv - x^{- 2}$

Then, based on the coefficient rotation technique in Summary A-5.2.1, rotating 1 position to the left is equivalent to computing $f \cdot x^{- 1}$ as follows:

$f \cdot x^{- 1} = 2 \cdot (x^{- 1}) + 3 x \cdot (x^{- 1}) - 4 x^{2} \cdot (x^{- 1}) - x^{3} \cdot (x^{- 1})$

$\equiv - 2 x^{3} + 3 - 4 x^{1} - x^{2}$

$= 3 - 4 x^{1} - x^{2} - 2 x^{3}$

As another example, rotating 3 positions to the left is equivalent to computing $f \cdot x^{- 3}$ as follows:

$f \cdot x^{- 3} = 2 \cdot (x^{- 3}) + 3 x \cdot (x^{- 3}) - 4 x^{2} \cdot (x^{- 3}) - x^{3} \cdot (x^{- 3})$

$\equiv - 2 x - 3 x^{2} + 4 x^{3} - 1$

$= - 1 - 2 x - 3 x^{2} + 4 x^{3}$

$= - 1 - 2 x - 3 x^{2} + (4 \equiv - 4 mod 8) x^{3}$

$\equiv - 1 - 2 x - 3 x^{2} - 4 x^{3}$

[prev][parent]