La factorisation 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 !
Exemple 1 :
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 !
Bien sûr, dans le cas général, en prenant des x juste plus grands que racine de n, il n'est pas sûr que l'on tombe dans le cas précédent. Mais on peut combiner plusieurs équations : si x12=a1 mod n,..., xp2=ap mod n, et que a1...ap=y2 mod n, en posant x=x1...xp, on retrouve x2=y2 mod n.
Exemple 2 :
Soit à factoriser n=180121, dont la racine carrée vaut 424, et des brouettes... En faisant des essais successifs avec les entiers juste supérieurs à 424, on trouve :
- 4252=2332527 mod n
- 4392=233272 mod n
Tout le problème réside ensuite dans le choix des bases de petits premiers sur lesquels on souhaite décomposer !