Algorithmes pour l'arithmétique
Cours : Claude-PierreJeannerod (Claude-Pierre.Jeannerod)
TD : Guillaume Melquiond (Guillaume Melquiond)
Ce cours est une introduction à la complexité et à l'algorithmique
des opérations de base sur les nombres le plus souvent implantés
en machine (entiers, nombres flottants, éléments d'un corps fini).
Il comportera trois parties:
-
Entiers, polynômes et séries.
Principaux paradigmes pour accélérer les calculs
(FFT et Karatsuba pour multiplier, Newton pour diviser).
Réduction entre problèmes et complexité des fonctions algébriques.
- Arithmétique "réelle" et continue.
Représentation des nombres (virgule fixe, virgule flottante, norme IEEE 754).
Exemple d'algorithmes (division et racine carrée).
Application au calcul flottant sur processeurs embarqués.
- Corps finis.
Différentes représentations des corps finis.
Algorithmes pour la multiplication, la division et l'exponentiation rapide.
Suites récurrentes linéaires et polynôme minimal.
Applications en cryptographie et en théorie des codes.
Bibliographie
-
P. Burgisser, M. Clausen, and M.A. Shokrollahi, Algebraic Complexity Theory, Springer 1997.
- M.D. Ercegovac and T. Lang, Digital Arithmetic, Morgan Kaufmann 2004.
- J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge 2003.
- D. Hankerson, A. Menezes, and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag, 2004.
- N. Higham, Accuracy and stability of numerical algorithms, SIAM 2002.
- D.E. Knuth, The Art of Computer Programming, Volume 2, Addison Wesley 1997.
- M. Overton, Numerical Computing with IEEE Floating Point Arithmetic, SIAM 2001.