programme Henri Cohen

Henri Cohen: Algorithmes de Primalité et de Factorisation

Les algorithmes de primalité et de factorisation ont toujours fasciné les mathématiciens, amateurs aussi bien que professionnels (Gauss lui-même par exemple). Depuis l'invention de la méthode de cryptographie à clef publique RSA, l'intérêt pour ces algorithmes a été renouvelé. Le but du cours est de donner une introduction assez détaillée aux diverses méthodes utilisées, qu'elles soient utilisables en pratique, ou bien de nature essentiellement théoriques.

Outils et réductions:
- Divisions successives.
- Le petit théorème de Fermat, qui conduit à distinguer 3 sortes de tests: les tests de non-primalité, les tests de primalité, les algorithmes de factorisation.
- Les courbes elliptiques: sur C, R, Q mais surtout sur les corps finis. Elles sont omniprésentes dans le sujet et fournissent à la fois un test de primalité (ECPP), un algorithme de factorisation (ECM) et une méthode cryptographique à clef publique (ECC).
Tests de non-primalité:
- Le test de Rabin--Miller.
Tests de primalité:
- Le test de Pocklington--Lehmer.
- L'algorithme AKS.
- Mention de l'algorithme APRCL.
- L'algorithme ECPP, du moins sous sa forme la plus simple.
Méthodes de factorisation:
- Méthode ro de Pollard.
- Méthode p-1 de Pollard.
- Méthode ECM de Lenstra.
- Méthodes QS et généralisations.
- Méthode NFS (esquisse).

Retour École de Cryptologie.