« Approfondissements de lycée/Premiers » : différence entre les versions
Contenu supprimé Contenu ajouté
→Introduction : wiki |
→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
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
<br />
Avec les développements récents,
</blockquote>
|