Source vérifiéeNiveau 4

Algorithme de Shor

L'algorithme de Shor factorise les grands entiers en temps polynomial O((log N)³), menacant RSA.

Le voir en mouvement

Après une inscription gratuite, vous revenez directement à ce concept.

Continuer dans l'app →J'ai déjà un compte

Ce que cela signifie

Reduit la factorisation a la recherche de periode par QFT.Motive la cryptographie post-quantique.

Analogie du quotidien

Comme trouver le rythme secret.
Comme trouver la frequence de resonance d'un coffre.

Idées reçues fréquentes

  • Ne casse pas instantanement toute encryption.
  • Les ordinateurs quantiques actuels ne peuvent pas l'executer.

À retenir

  • O((log N)³) factorisation.
  • Reduction a la recherche de periode par QFT.
  • Motive la cryptographie post-quantique.

Vérifiez votre compréhension

A quel probleme Shor reduit-il la factorisation?

  1. A.Multiplication matricielle
  2. B.Recherche de periode
  3. C.Coloration de graphe
  4. D.Tri
Voir la réponse

Réponse: B. Recherche de periode

Pourquoi: Reduction a la recherche de periode.

S’appuie sur

QubitSuperpositionTransformée de Fourier quantiqueMesure quantiqueIntrication quantique

Ce qui s’appuie dessus

ML-KEM (Encapsulation de clé par réseau modulaire)Migration post-quantique

Notions liées

Correction d'erreurs quantiquesRétroaction de phase (phase kickback)Estimation de phase quantique

Source primaire: Shor, SIAM J. Comput. 26, 1484 (1997), doi:10.1137/S0097539795293172

Hardware-status sentences ('current quantum computers cannot factor...') are explicitly era-qualified honesty statements protecting against hype; algorithm itself is established mathematics.

Apprendre en pratiquant

Ce concept fait partie d’un cursus de 46 niveaux, avec un simulateur interactif et Lumen — un tuteur qui contrôle ses réponses et indique leur degré de certitude. Les niveaux 1–5 sont gratuits.

Commencer gratuitementVoir le cursus