Computer Algebra, Fall Spring 2015, 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).
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]
- Introduction to lattice reduction and a short LLL implementation.
- Fast Fourier Transform.
- 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.
- Lets schedule a test next week, on the topics from weeks 7-10.
Groebner basis
Factoring Integers
Elementary integration