comme on ne sait pas bien quelle est la complexité de la factorisation mais que ce n'est sans doute pas NP
La factorisation est dans NP. On sait également qu'il est co-NP. Par contre, il n'est pas (co-)NP-difficile.
ça ne permettra pas encore de résoudre les problèmes les plus difficiles
On sait déjà que les problèmes NP-complets restent difficile même en quantique ; c'est pour ça que les cryptosystèmes post-quantiques se basent sur des sous-ensembles de problèmes NP-complets (on cherche des classes dont toutes les instances sont difficiles, là où NP-complet ne garantie que l' existence des telles instances).
De plus, en tant qu'avancée scientifique, si on a un ordinateur capable de factoriser de grands nombres, on casse toute la cryptographie actuelle (y compris celle basée sur les courbes elliptiques). Donc, même si il ne fait que ça, ça a déjà un impact énorme.
[^] # Re: Peut-être même à 6 chiffres !
Posté par aiolos . En réponse au journal [Quantique] La ligne des 49 qubits. Évalué à 6. Dernière modification le 29 mai 2017 à 09:16.
La factorisation est dans NP. On sait également qu'il est co-NP. Par contre, il n'est pas (co-)NP-difficile.
On sait déjà que les problèmes NP-complets restent difficile même en quantique ; c'est pour ça que les cryptosystèmes post-quantiques se basent sur des sous-ensembles de problèmes NP-complets (on cherche des classes dont toutes les instances sont difficiles, là où NP-complet ne garantie que l' existence des telles instances).
De plus, en tant qu'avancée scientifique, si on a un ordinateur capable de factoriser de grands nombres, on casse toute la cryptographie actuelle (y compris celle basée sur les courbes elliptiques). Donc, même si il ne fait que ça, ça a déjà un impact énorme.