Consider the following two polynomials in F_{17}[x]
(a) Use Karatsuba's algorithm, by hand, to multiply these two polynomials.
(b) Use the FFT algorithm, by hand, to multiply these two polynomials.
Remember that if a polynomial has degree 3 or less then it is irreducible if and only if it has at least one linear factor, that (x - a) is a linear factor of a polynomial f(x) if and only if f(a) = 0 and that for small elds it is easy to check by hand if a particular value is a root of a polynomial.
(a) Which of the following polynomials are reducible and irreducible in F_{5}[x]? What is the factorization of the reducible ones?
(b) Does the following system have a unique solution of smallest degree: