Factoriser en nombres premiers par ordinateur
Bonjour,
Vous connaissez la théorie : tout nombre se factorise en nombres premiers. C'est important : cryptographie, etc.
Or, naïvement, même avec des algorithmes simples, on peut arriver à factoriser des nombres assez grands en temps "pas trop long".
Alors, pourquoi dit-on que les ordinateurs n'arrivent pas à factoriser [en] nombres premiers des nombres plus grands que 200 environ ?
Vous connaissez la théorie : tout nombre se factorise en nombres premiers. C'est important : cryptographie, etc.
Or, naïvement, même avec des algorithmes simples, on peut arriver à factoriser des nombres assez grands en temps "pas trop long".
Alors, pourquoi dit-on que les ordinateurs n'arrivent pas à factoriser [en] nombres premiers des nombres plus grands que 200 environ ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Or le processeur de l'ordinateur que tu as sur les genoux a une fréquence de l'ordre de 3 GHz : il fait environ $3\cdot10^9$ cycles par seconde. Un ordinateur très puissant peut faire $10^{12}$ opérations par seconde (je me trompe peut-être d'un ordre de grandeur ou deux et ça n'a aucune importance). Il faut donc au moins \[\frac{10^{100}}{10^{12}}=10^{88}\ \text{secondes}\] pour factoriser un nombre de 200 chiffres avec cet algorithme naïf.
Rectification : l'âge de l'univers est estimé à environ $13$ milliards d'années, entre $10^{17}$ et $10^{18}$ secondes. Par conséquent, un tel calcul est impossible.
Il y a des algorithmes moins naïfs que ça mais ils ne sont pas assez efficaces pour vaincre cette impossibilité – pour l'instant au moins, cf. ce fil.
Et le problème, c'est que c'est difficile de faire des ordinateurs quantiques avec beaucoup de qbits.
x \mod N, \quad x^2 \mod N,\quad x^3\mod N,\quad x^4\mod N,\ldots
$$ On sait, grâce à Euler, que si $N=pq$ et si $x$ n'est pas divisible par $p$ et $q$, la suite se répète avec une période qui divise $(p-1)(q-1)$.
Une seule des 10 étapes de l'algorithme dépend d'un ordinateur quantique : celle qui utilise la transformée de Fourier quantique pour débusquer la période.
...
Ce dernier problème est difficile pour un algorithme classique.
Je n'ai pu attacher le fichier car il est trop lourd en mémoire mais il est facile à trouver:
$\textbf{"Efficient quantum algorithms for estimating Gauss sums"}$- Wim Van Dam, Gadiel Seroussi.
...