La France ne cesse de baisser dans les enquêtes PISA, qui évaluent le niveau en mathématiques des jeunes générations. Cédric Villani, médaillé Fields, a remis récemment un rapport pour rétablir la France dans ce classement. Pourtant, la France compte dans son histoire de nombreux mathématiciens d’importance. C’est le cas de Pierre de Fermat, fameux mathématicien, « prince des amateurs » qui avant ses 40 ans, en 1640, a démontré un théorème désormais éponyme : le petit théorème de Fermat. Ce théorème a à son tour été exploité par Ronald Rivest, Adi Shamir et Leonard Adelman, eux aussi de fringants trentenaires en 1977, année où ils mirent au point le fameux algorithme de chiffrement, lui aussi éponyme : RSA. Voyons ce qu’il y a de si remarquable dans ces maths qui n’impliquent que de simples opérations arithmétiques.
Nous allons exposer dans cet article le fonctionnement de l’algorithme de chiffrement RSA, et en détailler une implémentation simple en Go. Nous rentrerons ensuite dans les détails, et partirons à l’exploration de l’ensemble des nombres premiers.
1. De quoi je vous envoierois la démonstration, si je n’apppréhendois d’être trop long
1.1 Le petit théorème de Fermat
Pierre de Fermat, donc, Prince des amateurs, énonce, il y a de cela pas loin de 400 ans, ceci :
ap-1 - 1 ≡ 0 (mod p) si p est un nombre premier, et a n’est pas divisible par p.
Comme à son habitude, et au désespoir de son contemporain Descartes, Fermat ne donne pas de démonstration de son théorème. Visiblement, la chose coule de source pour Fermat, mais pour nous autres, simples développeurs, c’est une autre histoire. À bien y regarder, on ne voit pas trop à quoi ce théorème peut servir.
Heureusement, contrairement à ce malheureux Fermat, nous avons des...
- Accédez à tous les contenus de Connect en illimité
- Découvrez des listes de lecture et des contenus Premium
- Consultez les nouveaux articles en avant-première