Factoriser des entiers
La factorisation des entiers est un problème crucial en cryptographie, car elle permet de casser le RSA. La méthode la plus élémentaire pour factoriser un entier n consiste à prendre tous les entiers inférieurs à n, et à tester s'ils divisent n(=algorithme de force brute). C'est bien sûr un algorithme inutilisable si n est grand. Un premier raffinement consiste à ne prendre que les entiers inférieurs à racine de n (si n n'est pas premier, n admet forcément un diviseur inférieur à racine de n). C'est beaucoup mieux, mais encore insuffisant pour les entiers de 1000 chiffres que l'on souhaite factoriser. L'idée utilisée par les algorithmes modernes (crible quadratique, crible du corps de nombre) est due à l'arithméticien français Pierre de Fermat : si on trouve deux entiers x et y, non égaux, non opposés, tels que x2=y2 mod n, alors (x-y)(x+y)=0 mod n, et pgcd(x+y,n) ou pgcd(x-y,n) donne un diviseur non trivial de n. Il reste à trouver de tels nombres x et y. Posons x un nombre juste supérieur à racine de n. x2 est juste supérieur à n, et x2=a mod n, avec a petit. Il est donc facile de factoriser a, et avec un peu de chances, en essayant plusieurs x, on peut espérer trouver un a tel que a=y2. Et alors c'est fini! Ex : Soit à factoriser n=3337. Sa racine carrée vaut 57 et des brouettes... On teste :- 582=27=33 mod 3337 : ne convient pas.
- 592=144=122 mod 3337 : convient!
- 4252=2332527 mod n
- 4392=233272 mod n
Consulter aussi