← Retour à Q-LAB

Algorithme de Shor

Comprendre la factorisation quantique grâce à la recherche de période.

V0.9 · Démonstration pédagogique

1. Choisir un nombre

Choisis une base a entre 2 et N−1. Si a et N ont un facteur commun, la factorisation est immédiate.

2. Recherche de période

On étudie la fonction f(x) = aˣ mod N. La période r est le plus petit entier positif tel que aʳ mod N = 1.

PGCD(a, N)—
Période r—
Valeur a^(r/2) mod N—
Graphique des premières valeurs de f(x). La répétition illustre la périodicité.

3. Retrouver les facteurs

  1. Lance une démonstration pour afficher les étapes.

Ce qui est quantique — et ce qui ne l'est pas

Dans l'algorithme de Shor réel, la recherche de période exploite un circuit quantique et une transformée de Fourier quantique, puis un traitement classique permet d'obtenir les facteurs.

Ce module calcule la période classiquement pour rendre le mécanisme visible. Il ne simule pas le circuit quantique complet, ne mesure pas de qubits et ne prouve aucune accélération quantique.

Une base peut conduire à un échec : c'est un comportement normal de la méthode, et l'on peut essayer une autre base.