Computer Algebra, Spring 2018, course documents

syllabus

Weeks 1 and 2. Note: If your web-browser does not start Maple when clicking on these Maple files, then it may be easier to download all files for weeks 1 and 2 in this zip file weeks_1_2.zip, then unpack it on your computer. This creates a folder weeks_1_2 with the files in it (the file "files.txt" indicates in which order we're using them).

• 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.
• Another introduction to Maple and some exercises to test yourself (in the form of a pdf-file) with some of the answers.
• The Euclidean Algorithm.
• Programming assignment: multiplication of polynomials (this contains homework for week 2. Note: you may choose to do the assignment in this worksheet, or program the Karatsuba method instead).
• A sorting algorithm (called merge sort) based on the "divide and conquer" approach.
• Multiplying polynomials with the "divide and conquer" approach: the Karatsuba algorithm.

• Modular algorithms and the Chinese Remainder theorem.
• Study this program Modular algorithm for computing a determinant (don't worry about the complicated LinearAlgebra:-Modular commands, more important is to try to understand the overall setup; a bound B, a product m that should be at least 2B+1, and the chrem and mods(d,m) at the end). Here is an exercise for modular algorithms.
• The modular gcd algorithm. Read the worksheet The Extended Euclidean 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).
  • Do this assignment.
• Factoring in Fp[x].
• Short introduction to resultants.
• More details on resultants and an assignment.

• worksheet on p-adic numbers. For additional information 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.

• Lattices
• implementation for dimension 2 (this does not generalize to higher dimension, for that, we need the paper of Lenstra, Lenstra, and Lovasz).
• General strategy for using LLL.
• Different way to factor in Q[x].
• Yet another example.
• Assignment
  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]
• Assignment
  Write two programs that take as input a polynomial f in Z[x]. The output should be a non-trivial factor of f in Z[x], or "irreducible". The factor should be constructed with LLL using (in the first algorithm) one floating point root of f (computed with fsolve(f,x,complex) in Maple), and (in the second algorithm) one p-adic factor of f (computed with Factor(f) mod p, followed by Hensel lifting). For both algorithms, let the user specify the precision ("Digits" in the first algorithm, and a p-power in the second algorithm).

  In both cases, if the precision is too low, then the output could "irreducible" even if f is reducible. A p-adic precision that is provably high enough can be found in the LLL paper. With this bound one obtains a provably complete algorithm. Similarly, a floating point precision that is provably high enough was given by Schonhage.

• Assignment

  Use LLL to find a non-zero integer solution of the following equation: 35178*x^2-4115*y^2+18107*z^2 = 0 (I will explain in class how to turn this into a lattice problem).

• Applications and algorithm for lattice reduction with a short LLL implementation (study also its output).
• Let A := 1.84965176911448577697... Find rational numbers q1,q2,q3 with small numerators and denominators for which A is very close to q1*Pi + q2*sqrt(2) + q3*sqrt(3).
• Solutions of a polynomial.
• Study the worksheets on resultants above and the assignment on resultants that we did a little while ago (this worksheet may help: solving equations with resultants).
• Trager's factorization method for factoring over an algebraic extension of a field.
• Fast Fourier Transform.

• Here is a text file that explains the basic notion of polynomial ideals and Hilbert's Nullstellensatz.
• Solving polynomial equations, polynomial ideals: Groebner basis.
• Applications of Groebner basis.
• Assignments.
• another assignment and two more
• answers

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