Course on Computer Algebra: January - March 2003

General information

Aimed at:   4th and 5th year students in computer science and in mathematics

Lecturers:   T.H. Koornwinder and P. Moree

Time and place:   First session on Thursday, 9 January 2003, 11.15-13.00 in room P015A, Eucldes building.
Next, from Tuesday, 14 January onwards, on Tuesday, 9.15-11.00, room P017, Euclides building.

Literature:   J. von zur Gathen and J. Gerhard, Modern computer algebra,   Cambridge University Press, first edition, 1999.
See also the author's Addenda and corrigenda.

Content:   The topics of the course will be chosen from the book mentioned above. The choice of topics, and the emphasis to be given to applications (like cryptography) and to complexity issues will depend on the interest of the students. Possible theoretical topics (all having applications) are: Euclidean algorithm; fast multiplication; primality testing; Gröbner bases.

Remarks on prerequisites:   Facts needed from algebra (mainly elementary ring theory and field theory) will be explained during the course, but it is helpful if students already have read about this, for instance in the Appendix to the book mentioned above or in the syllabus Algebra 2(in Dutch) for the second year mathematics course Algebra 2.
See also the first year mathematics course Algebra 1 (mainly on group theory) with syllabus Algebra 1 (in Dutch).

Tutorials on Mathematica programming

Information about specific sessions (in Dutch)

1 april
Behandeld door P. Moree:
I briefly discuss the AKS-algorithm, a very recent algorithm that determines in polynomial time whether a given integer is prime or composite. I also discuss some aspects of prime number theory, in particular the Riemann Hypothesis (see also J. Brian Conrey, The Riemann hypothesis, Notices Amer. Math. Soc. 50 (2003), no. 3, pp. 341-353; if you want to join computing a possible counterexample, see www.zetagrid.net). Finally, the recent result by D. Goldston and C. Yildirim on Small gaps between consecutive primes will be briefly explained (added: the original paper has been withdrawn, but things could be corrected later.

18 maart
Behandeld door T. Koornwinder: Gröbner bases, vervolg (boek, Ch. 21)
Programmeeropdracht in Mathematica: Buchberger's algoritme om een Gröbner-basis te bepalen, zie pdf file.

11 maart
Behandeld door T. Koornwinder: Gröbner bases, vervolg (boek, Ch. 21)

4 maart
Behandeld door T. Koornwinder: Gröbner bases (boek, Ch. 21)
Programmeeropdracht in Mathematica: Delen met rest in meer variabelen, zie pdf file.

25 februari
Behandeld door P. Moree:
We bespreken testen om te bepalen of een getal al dan niet samensgesteld is (priemtesten). In het bijzonder de sterke pseudopriemtest. Begonnen zal worden met iets over cryptografie (RSA, Diffie-Hellman); de cryptografie levert de grootste impuls voor het ontwikkelen van priemtesten en factorisatiemethodes.
Zie verdere documentatie.
Programmeeropdracht in Mathematica: strong pseudoprimality test, zie text file.

18 februari
College is niet doorgegaan. Wel kan een pdf file gedownload worden door T.H. Koornwinder over het vermenigvuldigingsalgoritem van Schönhage en Strassen (§8.3 in het boek).

11 februari
Behandeld: Uit boek, Chapter 8: Fast Fourier Transform en Fast convolution of polynomials. Uit Chapter 9: Newton iteration.
Programmeeropdracht in Mathematica: Discrete Fourier transform;
zie pdf file;
zie ook text file met latere aanwijzing.

4 februari
Behandeld: Uit boek, Chapters 8 en 13: Karatsuba's multiplication algorithm, Fourier series, Discrete Fourier Transform, convolution of two polynomials (mod x^n-1).
Programmeeropdracht in Mathematica: Opgave 8.5 uit het boek (minstens (i), en (iv) voorzover het betrekking heeft op (i)).
Het is bij de implemetatie van Karatsuba's algoritme voor vermenigvuldiging van polynomen efficiënt om bij de iteratie naar lagere graden, zodra er polynomen van graad kleiner dan n0 (n0 experimenteel te bepalen: doorgaans 8 of 16 of 32) met elkaar vermenigvuldigd moeten worden, op de normale (naieve) manier van vermenigvuldiging over te gaan.
Bij tests kun je eventueel het Mathematica-commando Timing gebruiken.

28 januari
Behandeld: Vervolg chinese reststelling en relevante algebra (directe producten van ringen, ringhomomorfismen). Toepassing op polynomiale interpolatie problemen (Lagrange interpolanten).
Programmeeropdracht in Mathematica: Bereken determinant met geheeltallige entries met behulp van Chinese reststelling;
download text file met opdracht;
zie ook text file met latere aanwijzing.

21 januari
Behandeld: Modulair rekenen. Formulering van de chinese reststelling. Het efficiënt berekenen van a^N (mod m) door herhaaldelijk kwadrateren. Euler's uitbreiding van de kleine stelling van Fermat.
Programmeeropdracht in Mathematica: Implementeer Chinese reststelling; download text file.

14 januari
Behandeld: Voortzetting van Chapter 3:
Het uitgebreide euclidisch algoritme en de daarvoor relevante algebra (euclidische bereiken, idealen) alsmede iets over de complexiteit van dit algoritme (worst case, average case).
Programmeeropdracht in Mathematica: Vind de GCD van twee Gaussian integers.

9 januari
Behandeld: Begin van Chapter 3 (The Euclidean algorithm).
Programmeeropdracht in Mathematica:
Gegeven polynomen a(x) en b(x) met rationele coefficienten, vind polynomen q(x) en r(x) (graad van r(x) kleiner dan graad van b(x)) zo dat a(x) = q(x) b(x) + r(x).

Links

See further computer algebra links.


to Tom Koornwinder's home page