Chapter 17

Given a polynomial \(g \in R[X]\) and an element \(x \in R,\) a particularly elegant and efficient way of computing \(g(x)\) is called Horner's rule. Suppose \(g=\sum_{i=0}^{k-1} a_{i} X^{i},\) where \(k \geq 0\) and \(a_{i} \in R\) for \(i=0, \ldots, k-1 .\) Horner's rule computes \(g(x)\) as follows: $$ y \leftarrow 0_{R} $$ for \(i \leftarrow k-1\) down to 0 do $$ y \leftarrow y x+a_{i} $$ output \(y\) Show that this algorithm correctly computes \(g(x)\) using \(k\) multiplications in \(R\) and \(k\) additions in \(R\).

Let \(f \in R[X]\) be a polynomial of degree \(\ell>0\) with \(\operatorname{lc}(f) \in R^{*},\) and let \(E:=R[X] /(f) .\) Suppose that in addition to \(f,\) we are given a polynomial \(g \in R[X]\) of degree less than \(k\) and an element \(\alpha \in E,\) and we want to compute \(g(\alpha) \in E .\) This is called the modular composition problem. (a) Show that a straightforward application of Horner's rule yields an algorithm that uses \(O\left(k \ell^{2}\right)\) operations in \(R,\) and requires space for storing \(O(\ell)\) elements of \(R\). (b) Show how to compute \(g(\alpha)\) using just \(O\left(k \ell+k^{1 / 2} \ell^{2}\right)\) operations in \(R,\) at the expense of requiring space for storing \(O\left(k^{1 / 2} \ell\right)\) elements of \(R\). Hint: first compute a table of powers \(1, \alpha, \ldots, \alpha^{m},\) for \(m \approx k^{1 / 2}\)

Given polynomials \(g, h \in R[X],\) show how to compute their composition \(g(h) \in R[X]\) using \(O\left(\operatorname{len}(g)^{2} \operatorname{len}(h)^{2}\right)\) operations in \(R\).

Suppose you are given three polynomials \(f, g, h \in \mathbb{Z}_{p}[X],\) where \(p\) is a large prime, in particular, \(p \geq 2 \operatorname{deg}(g) \operatorname{deg}(h) .\) Design an efficient probabilistic algorithm that tests if \(f=g(h)\) (i.e., if \(f\) equals \(g\) composed with \(h\) ). Your algorithm should have the following properties: if \(f=g(h),\) it \(\begin{array}{ll}468 & \text { Polynomial arithmetic and applications }\end{array}\) should always output "true," and otherwise, it should output "false" with probability at least \(0.999 .\) The expected running time of your algorithm should be \(O\left((\operatorname{len}(f)+\operatorname{len}(g)+\operatorname{len}(h)) \operatorname{len}(p)^{2}\right)\) EXERCISE 17.6. Let \(x, a_{0}, \ldots, a_{\ell-1} \in R,\) and let \(k\) be an integer with \(0

Let \(x, a_{0}, \ldots, a_{\ell-1} \in R,\) and let \(k\) be an integer with \(0

Let \(F\) be a field. Show that given polynomials \(s, t \in F[X]\) and integer \(k,\) with \(\operatorname{deg}(s)<\operatorname{deg}(t)\) and \(k>0,\) we can compute the \(k\) th coefficient in the reversed Laurent series representing \(s / t\) using \(O\left(\operatorname{len}(k) \operatorname{len}(t)^{2}\right)\) operations in \(F\)

Let \(F\) be a field. Let \(z \in F\left(\left(X^{-1}\right)\right)\) be a reversed Laurent series whose coefficient sequence is ultimately periodic. Show that \(z \in F(X)\).

Let \(F\) be a field. Let \(z=s / t,\) where \(s, t \in F[X], \operatorname{deg}(s)<\operatorname{deg}(t)\) and \(\operatorname{gcd}(s, t)=1\). (a) Show that if \(F\) is finite, there exist integers \(k, k^{\prime}\) such that \(0 \leq k

This problem is the analog of Exercise 3.48 for \(R[X] .\) Let us first define the notion of a "floating point" reversed Laurent series \(\hat{z},\) which is represented as a pair \((g, e),\) where \(g \in R[X]\) and \(e \in \mathbb{Z}-\) the value of \(\hat{z}\) is \(g X^{e} \in R\left(\left(X^{-1}\right)\right),\) and we call len \((g)\) the precision of \(\hat{z} .\) We say that \(\hat{z}\) is a length \(k\) approximation of \(z \in R\left(\left(X^{-1}\right)\right)\) if \(\hat{z}\) has precision \(k\) and \(\hat{z}=(1+\varepsilon) z\) for \(\varepsilon \in R\left(\left(X^{-1}\right)\right)\) with \(\operatorname{deg}(\varepsilon) \leq-k,\) which is the same as saying that the high-order \(k\) coefficients of \(\hat{z}\) and \(z\) are equal. Show that given \(h \in R[X]\) with \(\operatorname{lc}(h) \in R^{*},\) and positive integer \(k,\) we can compute a length \(k\) approximation of \(1 / h \in R\left(\left(X^{-1}\right)\right)\) using \(O(M(k))\) operations in \(R\). Hint: using Newton iteration, show how to go from a length \(t\) approximation of \(1 / h\) to a length \(2 t\) approximation, making use of just the high-order \(2 t\) coefficients of \(h,\) and using \(O(M(t))\) operations in \(R\).

State and re-work the analog of Exercise 3.52 for \(R[X],\) assuming \(2_{R} \in R^{*}\)

Let \(g, h \in R[X, Y]\) with \(g=\sum_{i=0}^{m-1} g_{i} Y^{i}\) and \(h=\sum_{i=0}^{m-1} h_{i} Y^{i},\) where each \(g_{i}\) and \(h_{i}\) is a polynomial in \(X\) of degree less than \(k .\) The product \(f:=g h \in R[X, Y]\) may be written \(f=\sum_{i=0}^{2 m-2} f_{i} Y^{i},\) where each \(f_{i}\) is a polynomial in \(X .\) Show how to compute \(f,\) given \(g\) and \(h,\) using \(O(M(k m))\) operations in \(R\). Hint: for an appropriately chosen integer \(t>0,\) first convert \(g, h\) to \(\tilde{g}, \tilde{h} \in R[X],\) where \(\tilde{g}:=\sum_{i=0}^{m-1} g_{i} X^{t i}\) and \(\tilde{h}:=\sum_{i=0}^{m-1} h_{i} X^{t i} ;\) next, compute \(\tilde{f}:=\tilde{g} \tilde{h} \in R[X] ;\) finally, "read off" the \(f_{i}\) 's from the coefficients of \(\tilde{f}\).

Suppose \(2_{R} \in R^{*}\) and \(\omega \in R\) is a primitive \(2^{n}\) th root of unity. (a) Let \(k\) be any integer, and consider gcd \(\left(k, 2^{n}\right),\) which must be of the form \(2^{m}\) for some \(m=0, \ldots, n .\) Show that \(\omega^{k}\) is a primitive \(2^{n-m}\) th root of unity. (b) Show that if \(n \geq 1,\) then \(\omega-1_{R} \in R^{*}\) (c) Show that \(\omega^{k}-1_{R} \in R^{*}\) for all integers \(k \not \equiv 0\left(\bmod 2^{n}\right)\). (d) Show that for every integer \(k,\) we have $$ \sum_{i=0}^{2^{n}-1} \omega^{k i}=\left\\{\begin{array}{ll} 2_{R}^{n} & \text { if } k \equiv 0\left(\bmod 2^{n}\right) \\ 0_{R} & \text { if } k \neq 0\left(\bmod 2^{n}\right) \end{array}\right. $$ (e) Let \(M_{2}\) be the 2 -multiplication map on \(R^{\times 2^{n}},\) which is a bijective, \(R\) -linear map. Show that $$ \mathcal{E}_{n, \omega} \circ \mathcal{E}_{n, \omega^{-1}}=\boldsymbol{M}_{2}^{n}=\mathcal{E}_{n, \omega^{-1}} \circ \mathcal{E}_{n, \omega} $$ and conclude that \(\mathcal{E}_{n, \omega}\) is bijective, with \(M_{2}^{-n} \circ \mathcal{E}_{n, \omega^{-1}}\) being its inverse. Hint: write down the matrices representing the maps \(\mathcal{E}_{n, \omega}\) and \(\mathcal{E}_{n, \omega^{-1}}\).

This exercise develops a fast algorithm, called the fast Fourier transform or FFT, for computing the function \(\mathcal{E}_{n, \omega} .\) This is a recursive algorithm 17.6 Faster polynomial arithmetic (*) FFT \(\left(n, \omega ; a_{0}, \ldots, a_{2^{n}-1}\right)\) that takes as input an integer \(n \geq 0,\) a primitive \(2^{n}\) th root of unity \(\omega \in R,\) and elements \(a_{0}, \ldots, a_{2^{n}-1} \in R,\) and runs as follows: if \(n=0\) then return \(a_{0}\) else $$ \begin{array}{l} \left(\alpha_{0}, \ldots, \alpha_{2^{n-1}-1}\right) \leftarrow \mathrm{FFT}\left(n-1, \omega^{2} ; a_{0}, a_{2}, \ldots, a_{2^{n}-2}\right) \\\ \left(\beta_{0}, \ldots, \beta_{2^{n-1}-1}\right) \leftarrow \mathrm{FFT}\left(n-1, \omega^{2} ; a_{1}, a_{3}, \ldots, a_{2^{n}-1}\right) \\\ \text { for } i \leftarrow 0 \text { to } 2^{n-1}-1 \mathrm{do} \\ \quad \gamma_{i} \leftarrow \alpha_{i}+\beta_{i} \omega^{i}, \gamma_{i+2^{n-1}} \leftarrow \alpha_{i}-\beta_{i} \omega^{i} \\ \text { return }\left(\gamma_{0}, \ldots, \gamma_{2^{n}-1}\right) \end{array} $$

Assume \(2_{R} \in R^{*}\). Suppose that we are given two polynomials \(g, h \in R[X]\) of length at most \(\ell,\) along with a primitive \(2^{n}\) th root of unity \(\omega \in R,\) where \(2 \ell \leq 2^{n}<4 \ell .\) Let us "pad" \(g\) and \(h,\) writing \(g=\sum_{i=0}^{2^{n}-1} a_{i} X^{i}\) and \(h=\sum_{i=0}^{2^{n}-1} b_{i} X^{i},\) where \(a_{i}\) and \(b_{i}\) are zero for \(i \geq \ell\). Show that the following algorithm correctly computes the product of \(g\) and \(h\) using \(O(\ell \operatorname{len}(\ell))\) operations

This exercise uses the FFT to develop a linear-time algorithm for integer multiplication; however, a rigorous analysis depends on an unproven conjecture (which follows from a generalization of the Riemann hypothesis). Suppose we want to multiply two positive integers \(a\) and \(b\), each of length at most \(\ell\) (represented internally using the data structure described in \(\S 3.3\) ). Throughout this exercise, assume that all computations are done on a RAM, and that arithmetic on integers of length \(O(\operatorname{len}(\ell))\) takes time \(O(1) .\) Let \(k\) be an integer parameter with \(k=\Theta(\operatorname{len}(\ell)),\) and let \(m:=\lceil\ell / k\rceil .\) We may write \(a=\sum_{i=0}^{m-1} a_{i} 2^{k i}\) and \(b=\sum_{i=0}^{m-1} b_{i} 2^{k i},\) where \(0 \leq a_{i}<2^{k}\) and \(0 \leq b_{i}<2^{k} .\) Let \(n\) be the integer determined by \(2 m \leq 2^{n}<4 m\).

Let \(n\) be a large, positive integer. We can factor \(n\) using trial division in time \(n^{1 / 2+o(1)} ;\) however, using fast polynomial arithmetic in \(\mathbb{Z}_{n}[X],\) one can get a simple, deterministic, and rigorous algorithm that factors \(n\) in time \(n^{1 / 4+o(1)} .\) Note that all of the factoring algorithms discussed in Chapter \(15,\) while faster, are either probabilistic, or deterministic but heuristic. Assume that we can multiply polynomials in \(\mathbb{Z}_{n}[X]\) of length at most \(\ell\) using \(M(\ell)\) operations in \(\mathbb{Z}_{n},\) where \(M\) is a well-behaved complexity function, and \(M(\ell)=\ell^{1+o(1)}\) (the algorithm from Exercise 17.24 would suffice). (a) Let \(\ell\) be a positive integer, and for \(i=1, \ldots, \ell,\) let $$ a_{i}:=\prod_{j=0}^{\ell-1}(i \ell-j) \bmod n $$ Using fast polynomial arithmetic, show how to compute \(\left(a_{1}, \ldots, a_{\ell}\right)\) in time \(\ell^{1+o(1)} \operatorname{len}(n)^{O(1)}\) (b) Using the result of part (a), show how to factor \(n\) in time \(n^{1 / 4+o(1)}\) using a deterministic algorithm.