Peter Shor a décrit un algorithme de factorisation tirant parti de la nature des ordinateurs quantiques (superposition d'état) pour s'exécuter en un temps polynomial O(L2 L log L log log L) où L est le nombre de bits d'un nombre N. Cet algorithme est basé sur la recherche de période pour N via un transformé de Fourier.
Par ailleurs, il existe d'excellents algorithmes pour les ordinateurs classiques factorisant de grands entiers en des temps "raisonnablement" exponentiels comme le ECM (basé sur les courbes elliptiques, très étudiées en théorie des nombres et en théorie des codes) bien que trop lent pour s'attaquer à RSA, et surtout le Number Field Sieve (NFS) de Pollard (et d'autres) qui a effectué de nombreux travaux depuis 20 ans sur les algorithmes de factorisation. Le NFS s'exécute en un temps O(e1.9(ln n)1/3(ln ln n)2/3).
L'algorithme décrit par Bernstein est une optimisation (impressionante) du NFS comme il en est pratiquée depuis 10 ans. Pour mémoire RSA Security offre de 10000ドル à 200000ドル pour la factorisation de modulos RSA de 576 à 2048 bits.
En 1999, c'est déjà une variation du NFS qui avait permit de cracker RSA 155 (de 512 bits) en 97.5 années-cpu.
[^] # Re: Keep cool
Posté par vjm . En réponse à la dépêche Le RSA en danger. Évalué à 10.
http://www.research.att.com/~shor/papers/#quantum(...)
Par ailleurs, il existe d'excellents algorithmes pour les ordinateurs classiques factorisant de grands entiers en des temps "raisonnablement" exponentiels comme le ECM (basé sur les courbes elliptiques, très étudiées en théorie des nombres et en théorie des codes) bien que trop lent pour s'attaquer à RSA, et surtout le Number Field Sieve (NFS) de Pollard (et d'autres) qui a effectué de nombreux travaux depuis 20 ans sur les algorithmes de factorisation. Le NFS s'exécute en un temps O(e1.9(ln n)1/3(ln ln n)2/3).
http://mathworld.wolfram.com/NumberFieldSieve.html(...)
L'algorithme décrit par Bernstein est une optimisation (impressionante) du NFS comme il en est pratiquée depuis 10 ans. Pour mémoire RSA Security offre de 10000ドル à 200000ドル pour la factorisation de modulos RSA de 576 à 2048 bits.
En 1999, c'est déjà une variation du NFS qui avait permit de cracker RSA 155 (de 512 bits) en 97.5 années-cpu.
http://www.rsasecurity.com/rsalabs/challenges/factoring/(...)
Bref, belle découverte, mais pas de panique.
http://www.crypto-world.com/FactorPapers.html(...)