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
Weeks 7 - 10.
- 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
- 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
- Yet another example.
m := 13^30; f1 :=
Find a polynomial g in Z[x] such that:
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]
- 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.
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.
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.