« Approfondissements de lycée/Premiers » : différence entre les versions

Contenu supprimé Contenu ajouté
→‎Décomposition : reformulation + wiki
Ligne 52 :
 
=== Décomposition ===
Nous savons, à partir du théorème fondamental de l'arithmétique que tout nombre entier peut être exprimé comme un produit de nombres premiers. La question qu'on peut maintenant se poser est la suivante: pour un nombre donné ''x'', existe-t'il une manière ''facile'' de trouver tous les facteurs premiers de ''x'' ?
 
Si ''x'' est un petit nombre, c'est facile. Par exemple 90 = 2 x 3 x 3 x 5. Mais si ''x'' est grand ? Par exemple ''x = 4539'' ? La plupart des gens ne peuvent pas décomposer 4539 en facteurs premiers dansde leurs têtestête. Mais un ordinateur le peut-il, ?quasi Ouiinstantanément, unpour ordinateurdonner peutce décomposer 4539 instantanément. En fait,résultat: 4539 = 3 x 17 x 89.
 
Puisque les ordinateurs sont très bons pour faire de l'arithmétique, nous pouvons extraire tous les facteurs de ''x'' en indiquant simplement à l'ordinateur de diviser ''x'' par 2 et par 3 et par 4 et par 5 et par 6 ... et ainsi de suite, et vérifier si à chaque fois le résultat est un nombre entier. Considérons les trois exemples suivants de la méthode des divisions en action.
Ligne 107 :
==== info — Décomposition en facteurs premiers ====
<blockquote style="padding: 1em; border: 2px dotted purple;">
Il existe une manière ''facile'' de décomposer un nombre en facteurs premiers. En appliquant simplement la méthode décrite ci-dessus (en utilisant un ordinateur). Mais la méthode ci-dessus est trop lente pour les grands nombres : essayer de décomposer un nombre avec des milliers de chiffres prendrait plus de temps que l'age actuel de l'univers. Mais existe-t'il une manière ''rapide'' ? Ou plus précisément, existe-t'il une manière ''efficiente'' ? Cela se peut, mais personne ne l'a encore trouvée, ni même prouvé qu'elle existe. Certains des schémas de cryptologie les plus largement utilisés aujourd'hui (tel que le [http://fr.wikipedia.org/wiki/Rivest_Shamir_Adleman RSA]) utilisent le fait que nous ne pouvons pas décomposer des grands nombres en facteurs premiers rapidement. Si une telle méthode est trouvée, 90 % des transactions sur internet serontdeviendront non sécurisées. Donc, s'il vous arrive de découvrir une telle méthode, ne soyez pas trop empressé de la publier, consultez votre ministère de sécurité nationale avant !
<br />
 
Avec les développements récents, nousdes pouvonsméthodes qui ne déterminent pas ''directement'' si un nombre est premier ou non, mais donnent une ''proabilité'' qu'il soit premier, ont été définies. Ce méthodes sont aujourd'hui suffisamment affinées pour pouvoir dire rapidement, avec l'aide d'un programme informatique, si un nombre est premier avec 100%une précision proche de précision100%.
</blockquote>