🔐 Factorisation de Grands Nombres

ClĂ© de la Cryptographie RSA — Classique vs Algorithme de Shor (Quantique)
3 599
🔒 RSA repose sur ce problùme
Vitesse : 5
đŸ–„ïž
Classique — Division par Essais
Diviseur testé—
Tentatives0
ComplexitĂ© estimĂ©e—
⏳ En attente...
⚛
Quantique — Algorithme de Shor
Phase actuelle—
Appels Ă  l'oracle0
ComplexitĂ© estimĂ©e—
⏳ En attente...
📈 Explosion du nombre d'opĂ©rations selon la taille de N
Classique O(√N)
Quantique Shor O((log N)Âł)
📊 RĂ©sultats — Comparaison pour N =
đŸ–„ïž Classique
⚛ Quantique
⚡ Pour une clĂ© RSA-2048, le classique nĂ©cessiterait 10300 annĂ©es. Shor le rĂ©soudrait en quelques heures sur un ordinateur quantique suffisant.

🔐 Pourquoi la factorisation est-elle si importante ?

đŸ–„ïž Division par essais (classique)
Pour factoriser N, l'ordinateur essaie de le diviser par 2, 3, 4, 5
 jusqu'Ă  trouver un diviseur. Dans le pire cas, il faut tester jusqu'Ă  √N valeurs. Pour N = 3 599 : √3599 ≈ 60 essais. Pour une clĂ© RSA-2048 (N ≈ 10617) : √N ≈ 10308 essais — impossible mĂȘme en milliards d'annĂ©es.

ComplexitĂ© : O(√N) — exponentiel en bits.
⚛ Algorithme de Shor (quantique)
Shor utilise la TransformĂ©e de Fourier Quantique (QFT) pour trouver la pĂ©riode de la fonction f(x) = ax mod N. La pĂ©riode r rĂ©vĂšle les facteurs via pgcd(ar/2±1, N). GrĂące Ă  la superposition, toutes les valeurs de x sont Ă©valuĂ©es simultanĂ©ment. Pour RSA-2048 : ~(2048)Âł ≈ 8 milliards d'opĂ©rations — faisable !

ComplexitĂ© : O((log N)Âł) — polynomial en bits.
⚠ Enjeu mondial : Toute la sĂ©curitĂ© d'internet (HTTPS, banques, messageries) repose sur l'impossibilitĂ© de factoriser de grands nombres rapidement. Un ordinateur quantique suffisamment puissant (des milliers de qubits stables) rendrait l'actuel chiffrement RSA obsolĂšte — d'oĂč la course mondiale Ă  la cryptographie post-quantique.