Factorisation d'un nombre entier

« Factorisation d'un nombre entier » expliqué aux enfants par Vikidia, l’encyclopédie junior
Aller à : navigation, rechercher

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[modifier | modifier le wikicode]

Tout entier naturel est le produit de nombres premiers. Ce produit est unique à l'ordre près des facteurs.

Algorithmes de factorisation[modifier | modifier le wikicode]

Utilisations en cryptographie[modifier | modifier le wikicode]

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.

Portail des mathématiques —  Les nombres, la géométrie et les grands mathématiciens.