# Assignment 2

###
CS 680-503 Computer Algebra I

Instructor: Jeremy Johnson

Due Wed. Apr. 19 in class

### Problems to hand in

- 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).