30 ans de factorisation d'entiers

Factoriser les entiers est un sport vieux comme le monde. Il y a 30 ans, deux chercheurs s'attaquaient à la factorisation du nombre mythique $F_7 = 2^{2^7}+1$. Quelques années plus tard, la cryptographie à clefs publiques naissait, et avec elles le fameux cryptosystème RSA. Même si la sécurité de RSA n'est pas équivalente à la factorisation des entiers, factoriser la clef publique de RSA reste le moyen le plus simple de casser complètement le système. Soudainement, tout le monde se mettait ainsi à essayer de factoriser. En 1990, $F_9 = 2^{2^9}+1$ tombe sous les coups de boutoir de plusieurs centaines de machines. En août 1999, c'est le premier nombre {\em quelconque} de 512 bits qui rend les armes. Le but de cet exposé est de faire un survol de ces trente années de factorisation, en replaçant le problème dans son contexte cryptographique. On décrira les méthodes modernes utilisées pour factoriser, ainsi que les problèmes de nature technologique qu'il faut résoudre.