# Assignment 2

###
CS 680-503 Computer Algebra I

Instructor: Jeremy Johnson

Due Wed. May 17 in class

### Problems to hand in

- Trace through Yun's algorithm for squarefree factorization when applied
to the polynomial A = B_1 * B_2^2 * B_3^3 * B_4^4. Psuedocode for the
algorithm is provided in the section on squarefree factorization in
chapter 8 of the text (p. 342). Explain why Yun's algorithm might
be more efficient than the algorithm on p. 340 that we discussed in
class.
- In class we showed how to left a factorization mod p to a factorization
mod p^k using Hensel's lemma. Perform a computing time analysis
for the linear Hensel lifting shown in class. Let A be a squarefree
integral polynomial. A = A1*A2 mod p, deg(A) = n, deg(A1) = n1,
deg(A2) = n2, |A|_1 = d. Find the maximum computing time as a function
n, n1, n2, d, and k to lift the factorization mod p to a factorization
mod p^k.
- Determine a bound on k from part 1 using Mignotte's factor coefficient
bound. And plug this into the bound from part 1.
- [Extra credit] Implement the two squarefree factorization algorithms
discussed in question 1, and empirically compare their computing time.
- [Extra credit]
Suppose A = A1 * ... * Ar mod p. The factors Ai can be lifted by
lifting the factorization A = Ai * (A/Ai) mod p. Devise an algorithm
to lift all r factors (using Hensel's lemma). What is the total
time to lift all r factors?