# Computer Algebra, Spring 2018, course documents

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).

Weeks 3 - 6
• 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.
Weeks 7 - 10.
• 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.
Groebner basis
Factoring Integers Elementary integration