Source vérifiéeNiveau 4

Algorithme de Shor

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

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

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 dont les réponses sont vérifiées avant affichage. Les niveaux 1–5 sont gratuits.

Commencer gratuitementVoir le cursus