Assignment 2

CS 680-503 Computer Algebra I
Instructor: Jeremy Johnson 
Due Wed. May 17 in class

Problems to hand in

  1. 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.
  2. 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.
  3. Determine a bound on k from part 1 using Mignotte's factor coefficient bound. And plug this into the bound from part 1.
  4. [Extra credit] Implement the two squarefree factorization algorithms discussed in question 1, and empirically compare their computing time.
  5. [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?