Question

Let \(F=F_{17}\) and \(f=5 x^{3}+3 x^{2}-4 x+3, g=2 x^{3}-5 x^{2}+7 x-2\) in \(F|x|\) (i) Show that \(\omega=2\) is a primitive 8th root of unity in \(F\), and compute the inverse \(2^{-1}\) mod 17 of \(\omega\) in \(\boldsymbol{F}\). (ii) Compute \(h=f \cdot g \in F[x]\). (iii) For \(0 \leq i<8\), compute \(\alpha_{i}=f\left(\omega^{i}\right), \beta_{i}=g\left(\omega^{i}\right)\), and \(\gamma_{i}=\alpha_{i} \cdot \beta_{i}\). Compare \(\gamma_{i}\) to \(h\left(\omega^{i}\right)\). (iv) Show the two matrices \(V_{1}=V_{\omega}\) and \(V_{2}=8^{-1} V_{\omega}-i\), and compute their product. Compute the matrix-vector products \(V_{1} \alpha, V_{1} \beta\), and \(V_{2} \gamma\), with vectors \(\alpha=\left(\alpha_{i}\right)_{0 \leq i<8,} \beta=\left(\beta_{i}\right)_{0} s_{i<8_{*}}\) and \(\gamma=(\gamma)_{0 \leq i<8}\) as computed. Comment. (v) Trace the FFT multiplication algorithm \(8.16\) to multiply \(f\) and \(g\), with \(\omega\) as above.

Short answer

(i) \( 2^{-1} \equiv 9 \mod{17} \). (ii) \( h(x) = 10x^6 + x^5 + 3x^4 + 10x^3 + 4x^2 + 12x + 6 \mod{17} \). (iii) Check \( \gamma_i \equiv h(\omega^i) \). (iv) Compute matrix-vector products. (v) Follow FFT multiplication algorithm.

Step-by-step solution

Verify primitive 8th root

Since \( \omega = 2 \) is a primitive 8th root of unity, we need to check that \( \omega^8 \equiv 1 \mod{17} \), and \( \omega^k ot\equiv 1 \mod{17} \) for \( k < 8 \). Calculating powers, we find:\( \omega^2 = 4 \), \( \omega^4 = 16 \equiv -1 \mod{17} \), therefore \( (\omega^4)^2 = \omega^8 = 1 \mod{17} \). Since none of the other powers are congruent to 1 before the 8th power, \( \omega = 2 \) is a primitive 8th root of unity.

Compute Inverse of 2 modulo 17

To find the modular inverse of \( \omega = 2 \) in \( \mathbb{F}_{17} \), we need to solve \( 2x \equiv 1 \mod{17} \). Using the extended Euclidean algorithm, we find:\[2x + 17(-x) = 1 \implies x = 9\]Thus, \( 2^{-1} \equiv 9 \mod{17} \).

Multiply Polynomials

We compute \( h = f \cdot g \) in \( \mathbb{F}_{17}[x] \):\[h(x) = (5x^3 + 3x^2 - 4x + 3)(2x^3 - 5x^2 + 7x - 2)\]Perform polynomial multiplication and reduce coefficients modulo 17. After simplification, we have:\[h(x) = 10x^6 + 1x^5 + 3x^4 + 27x^3 - 13x^2 + 29x + 6 \equiv 10x^6 + x^5 + 3x^4 + 10x^3 + 4x^2 + 12x + 6 \mod{17}\]

Evaluate Polynomials at Powers of Omega

For \( 0 \leq i < 8 \), calculate \( \alpha_i = f(\omega^i) \) and \( \beta_i = g(\omega^i) \) using substitution into each polynomial, reducing results modulo 17. Also, compute \( \gamma_i = \alpha_i \cdot \beta_i \mod{17} \).

Compare Gamma and h at Powers of Omega

Compute \( h(\omega^i) \) and compare it against \( \gamma_i \) for all \( i \). Ensure that \( \gamma_i \equiv h(\omega^i) \mod{17} \) for all \( 0 \leq i < 8 \). This verifies the point-wise product matches the evaluated product polynomial.

Matrix Construction and Multiplication

Construct the Vandermonde matrices \( V_1 = V_{\omega} \) and \( V_2 = 8^{-1}V_{\omega^{-1}} \). Compute matrix products \( V_1\alpha \), \( V_1\beta \), and \( V_2\gamma \) using the vectors \( \alpha, \beta, \gamma \) from previous steps. Observe their relationship and consistency with expected outcomes of polynomial product.

Tracing the FFT Multiplication Algorithm

Illustrating the Fast Fourier Transform algorithm \( 8.16 \): Start with evaluating \( f(x) \) and \( g(x) \) at powers of \( \omega \), computing point-wise products to form new polynomial, and then inverse FFT to synthesize result back from point values, aiming to achieve \( h = f \cdot g \). Check the intermediate steps for correctness against calculated values.

Key concepts

Primitive Roots of Unity

In the world of finite fields, a primitive root of unity is a special kind of number. Specifically, for a finite field, a primitive nth root of unity is an element \( \omega \) such that \( \omega^n = 1 \) and \( \omega^k eq 1 \) for any positive integer \( k < n \). In simpler terms, it's the smallest power that makes \( \omega \) equal to 1 when using modular arithmetic.
For example, as given in the exercise, \( \omega = 2 \) is a primitive 8th root of unity in the field \( \mathbb{F}_{17} \). This means that \( 2^8 \equiv 1 \mod 17 \), and no smaller power of 2 achieves this equivalence. Buchholz, this property is crucial, especially in polynomial evaluations and transformations like the Fast Fourier Transform (FFT).
Why does this matter? Primitive roots help refine the process of evaluating and transforming polynomials over finite fields. They are fundamental in algorithms like FFT that simplify computations when working with polynomials and modular arithmetic.

Polynomial Multiplication

Polynomial multiplication is a key operation in algebra and cryptography. It involves taking two polynomials and producing a third polynomial, which is the product of the first two.
When multiplying polynomials like \( f = 5x^3 + 3x^2 - 4x + 3 \) and \( g = 2x^3 - 5x^2 + 7x - 2 \) in \( \mathbb{F}_{17}[x] \), every term of one polynomial is multiplied by every term of the other polynomial. Then, like terms are combined, and the resulting polynomial is reduced modulo 17 so that all coefficients are within the finite field limits.
This technique leads to a new polynomial \( h \), which in the problem was computed to be \( 10x^6 + x^5 + 3x^4 + 10x^3 + 4x^2 + 12x + 6 \). This reduction ensures that all operations remain within the bounds of the finite field \( \mathbb{F}_{17} \), offering a consistent framework for computation.

Fast Fourier Transform Algorithm

The Fast Fourier Transform (FFT) algorithm is a powerful tool for polynomial multiplication. It significantly speeds up the multiplication by transforming polynomial evaluations from polynomial space into a value space using roots of unity.
The essential idea is to evaluate a polynomial at distinct points, namely the powers of a primitive root of unity, to transform it into its "point-value" form. In the context of finite fields, this process utilizes the properties of roots of unity, allowing polynomial multiplication to be as simple as point-wise multiplication of their values at these points.
After multiplying these values, the inverse FFT converts the product back into a polynomial via inverse transformation. This makes polynomial multiplication through FFT highly efficient, especially for very large polynomials, reducing the complexity from slow multiplication processes to faster operations that take advantage of the symmetries offered by the roots of unity.

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value, known as the modulus. This is similar to the idea of a clock, which wraps around after 12 hours.
In the case of finite fields such as \( \mathbb{F}_{17} \), all calculations are performed modulo 17. Hence, any number is effectively reduced to its remainder after division by 17. For instance, working out the inverse of a number requires finding another number such that their product is equivalent to 1, modulo 17.
Thus, in the problem, to find the inverse of 2 in \( \mathbb{F}_{17} \), we solved \( 2x \equiv 1 \mod 17 \), which gave us 9. This shows how modular arithmetic keeps computations within the field, ensuring they adhere to field properties and maintain algebraic structure, which is especially relevant when working with things like polynomial roots, multiplications, and transformations.