Je sais, vous allez être déçu, mais RSA et la facatorisation sont deux problèmes différents.
RSA repose sur la factorisation, ce qui fait que si on trouve un algorithme polynomial pour factoriser, RSA est cassé.
MAIS on ne sait pas si il y a besoin de factoriser pour casser RSA.
Par exemple, il existe des nombres premiers particuliers (je ne me souviens plus de leur nom) qu'il faut absolument éviter de choisir quand tu génères tes clés sans quoi tu peux casser RSA sans avoir à factoriser.
Par ailleurs, il existe d'autres algorithmes, bien plus performants que ceux dont tu parles pour factorise (tester tous les nombres premiers inférieurs à sqrt(n)) : le crible quadratique et le crible algébrique.
[^] # RSA != factorisation
Posté par pappy . En réponse à la dépêche Un nombre premier exécutable ... illégal ?. Évalué à 2.
RSA repose sur la factorisation, ce qui fait que si on trouve un algorithme polynomial pour factoriser, RSA est cassé.
MAIS on ne sait pas si il y a besoin de factoriser pour casser RSA.
Par exemple, il existe des nombres premiers particuliers (je ne me souviens plus de leur nom) qu'il faut absolument éviter de choisir quand tu génères tes clés sans quoi tu peux casser RSA sans avoir à factoriser.
Par ailleurs, il existe d'autres algorithmes, bien plus performants que ceux dont tu parles pour factorise (tester tous les nombres premiers inférieurs à sqrt(n)) : le crible quadratique et le crible algébrique.
Tu trouveras ds référecnes sur cette page :
http://www.lix.polytechnique.fr/Labo/Francois.Morain/Crypto/crypto.(...)