Factorisation d’entiers : la voie royale du cassage de RSA

1 Introduction : émergence d’une communauté

De tous temps, il s’est trouvé des mathématiciens pour aimer faire des calculs que d’aucuns trouvaient anecdotiques, voire inutiles. Ces passionnés passaient de longs jours, à la main, à prouver la primalité de grands entiers (souvent de la forme 2p−1), calculer des zéros de la fonction de Riemann, factoriser des entiers, faire des tables de polynômes. Cela les a souvent conduits à inventer des méthodes astucieuses qui pour certaines n’ont pu être mises en œuvre avec succès qu’à partir du moment où des ordinateurs ont été disponibles.

La factorisation des entiers a donc sa préhistoire (cf. [WS94]), et son histoire récente est liée à l’informatique. La théorie de la complexité a été formalisée dans le but de classifier les problèmes à résoudre en fonction de leur facilité ou leur…