Assignment 2

In class we showed that if A(x) = a_n x^n + ... + a_1 x + a_0 is an integral polynomial with roots alpha_1,...,alpha_n, then B(x) = a_n^(n-1)A(x/a_n) is a monic integral polynomial. That is, a polynomial whose leading coefficient is one. Moreover, the roots of B(x) are a_n*alpha_i. Devise an algorithm for computing B(x) and determine its computing time.
Determine the computing time of the algorithm IPRZL, from the paper by Loos, if instead of adjusting rational roots in step (5), the input polynomial A(x) is first transformed as in question 1 before applying the linear lifting in step 4. Step (5) would then divide each root obtained in step 4 by dividing by a_n.
Implement (in either Maple or C and SACLIB) the linear and quadratic versions of the algorithm for lifting roots mod p to roots mod p^N. Empirically compare their efficiency and compare the empirical runtimes to the theoretical computing time bounds (the bounds for just the lifting).