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