Karim Belabas

Master Math, Algorithmic Number Theory (N1MA9W11) - 2014/2015

Bordeaux University / Mathematics

Note: Documents can differ from the ones handed in class (format change, typos). LaTeX style files [kb.sty | kbexo.sty] are needed to compile the TeX files (UTF-8 encoded).

The lectures take place on Thursdays 10am-12am and 2pm-4pm (Lamartine, salle de l'École).
First lecture on Thursday Sep. 10th.
We will be using the PARI/GP system. Here are the reference card and the GP User's guide.

Some course notes: [PDF] The exam in [2013-2014].

Road map

Lecture 1	Algorithms, Complexity, Examples
Lecture 2	The Fast Fourier Transform and basic complexity results
Lecture 3	Z-modules/HNF
Lecture 4	Z-modules/SNF & lattices
Lecture 5	The LLL Algorithm
Lecture 6	Polynomials over finite fields (1)
Lecture 7	Polynomials over finite fields (2)

Documents

The seminal LLL paper by Arjen Lenstra, Hendrik Lenstra Jr. and László Lovász (Math. Annalen, 1982).
Phong Nguyen and Damien Stehlé's floating point LLL.
Arne Storjohann's PhD thesis and his preprint on space efficient HNF.
A nice rendition by Dan Bernstein of the AKS primality test.
A survey of mine (in french) about computational algebraic number theory, and a more difficult paper (in english) on the same subjects.
François Morain's paper on his implementation of FastECPP.

Karim Belabas
2025-08-10 15:42:15