Computer Algebra, Spring 2002.

Note: I have moved to another office: 211 LOV

• We will look at this Maple worksheet on sequences in class.
• We will look at this worksheet on polynomials and the use of the quotes: ' ' in class. If there's enough time we'll also look at the following worksheets: worksheet on rational functions, worksheet on modular arithmetic. Study the remaining worksheets for next time.
• Homework week 1.
• Programming in Maple.
• Modular gcd algorithm

• Study the algorithms in this worksheet and do the assignment about sqrfree. The worksheet explains how the following algorithms work:
  • The Extended Euclidean Algorithm (only implemented for the case of positive integers, but it works in the same way for polynomials).
  • How to do divisions modulo an integer p. Note: one can use a similar algorithm to do divisions modulo a polynomial.
  • How to compute quotients and remainders.
  • Euclidean Algorithm for polynomials.
  • Chinese Remainder Theorem (only implemented for two integer moduli m1,m2. Of course a very similar algorithm would work when m1,m2 are polynomials).
• We'll start on this assignment in class, finish it at home.

• The completion of a field with respect to a norm (if this webpage does not display correctly under Netscape under Unix then click here).
• worksheet on p-adic numbers. For additional information see chapters 9 and 15 in the book, or see the worksheet on Factoring polynomials in Q[x] below.
• worksheet on x-adic Hensel lifting.

• Factoring polynomials in Q[x].
• Project: Implement factorization in Q[x,y] in the same way as factorization in Q[x] is done in the worksheet. You may use Maple's "sqrfree" for squarefree factorization, and may only use Maple's "factor" for factoring univariate polynomials. Replace "icontent" by "content", replace p-adic Hensel lifting by x-adic Hensel liften, replace the bound on the length of the coefficients by a bound on the degree of the coefficients, etc. Turn the Hensel lift algorithm from the worksheet on p-adic numbers into a Hensel lift algorithm for the x-adic case. This project is part of test 1.
• Study these worksheets at home: introduction to resultant, definition of resultant, properties of the resultant.

• Factoring in Fp[x].
• Lattices.
• General strategy for using LLL.
• Different way to factor in Q[x].
• Yet another example..
• Assignment (turn in before next wednesday)
  m := 13^30; f1 := x^2+186754841457272102163578030635634*x+46880804142885485944842413874037;
  Find a polynomial g in Z[x] such that:
  • degree(g) < 8
  • coefficients of g have absolute values less than 300.
  • f1 divides g modulo m. So Rem(g, f1, x) mod m; is zero.
  Hint: Use the same method as in the second example of the last worksheet, but then add two vectors, namely C*[0 0 0 .. 0 m 0] and C*[0 0 0 .. 0 0 m]
• Lattice reduction algorithm for dimension 2.
• Trager's factorization method for factoring over an algebraic extension of a field.
• Solutions of a polynomial.
• Study the worksheets on resultants. Then look at solving equations with resultants.
• assignment.

• Pollard's p-1 method for factoring integers
• Elliptic curves