Assignment 2

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?