Que feriez-vous si vous inventiez un algorithme capable de factoriser n'importe quel nombre semi-premier quasi-instantanément ?

Réponse publiée sur Quora

Je le publierais car ce serait la célébrité immédiate et une avancée majeure dans le Problème P ≟ NP (même si la factorisation n’a pas formellement été établie comme étant un problème NP)

Comme indiqué par Olivier Galand dans sa réponse , ça aurait des conséquences quasi immédiates en cryptographie, mais pas autant qu’on l’imagine car :

1. le Chiffrement RSA n’est pas si généralisé que ça. En fait on l’utilise surtout pour l’échange de clés symétriques, que l’on peut désormais faire autrement (voir plus bas)
2. L’industrie s’attend à ce que ce soit possible dans quelques années grâce aux ordinateurs quantiques. Il y a donc une recherche importante en Cryptographie post-quantique et des alternatives à RSA comme NTRUEncrypt sont déjà disponibles (et peut-être utilisées, je ne sais pas)

Pour la petite histoire, J’ai assisté à une présentation d’IBM sur l’informatique quantique aux alumni informaticiens EPFL, et quand le type a dit “la factorisation quantique ce sera dans 5 à 10 ans selon nos estimations, donc dans la prescription légale…” il y a eu un silence de mort chez mes collègues banquiers qui se tortillaient sur leurs chaises : toute entité (NSA, IRS ou autre) qui aurait eu l’idée saugrenue de stocker des messages cryptés pourra les décrypter et intenter des actions en justice avant qu’il y ait prescription… Je ne serais donc pas étonné que nos amis banquiers passent au post-quantique encore plus vite que les militaires.