Factorisation d'un nombre entier
Un nombre entier est premier s'il n'existe aucun entier naturel le divisant autre que 1 et lui-même. La factorisation d'un entier naturel est son écriture comme un produit de nombres permiers. Cette écriture existe toujours : c'est le théorème fondamental de l'arithmétique. Mais ce théorème ne dit pas comment trouver efficacement la factorisation.
Théorème fondamental de l'arithmétique
- Tout entier naturel est le produit de nombres premiers. Ce produit est unique à l'ordre près des facteurs.
Algorithmes de factorisation
Utilisations en cryptographie
En cryptographie à clef publique, elles représentent deux nombres premiers distincts qui permettent de créer le modulo en faisant le calcul n = p × q, où n est le modulo. Décoder un message est immédiat si on connaît p et q ; impossible sinon lorsque n est trop grand. Les procédés de codage à clef publique comptent sur le fait que retrouver p et q à partir de n, quand n est très grand (vers les 100 chiffres), est impossible pour les ordinateurs actuels.
Les nombres premiers p et q sont choisis distincts. Il existe des méthodes efficaces d'extraction de la racine carrée ; autrement dit qui donnent une approximation de la racine carrée de n.
Question : Comment trouver un entier n à environ 100 chiffres qui se factorise en deux nombres premiers distincts ?
Réponse : En prenant la produit de deux nombres premiers à environ 50 chiffres.
|
