Discussion :

[chaa13]

Bonjour,

J'essaye d'implémenter moi même RSA en C++, le problème vient lors de la generation des deux nombre premiers, je génère un nombre aléatoirement dans un intervalle donné, et je vérifie si il est premier avec le test de primalité de Fermat (ce qui, je crois est la méthode employé de nos jours pour beaucoup d'implémentation de RSA), je fais 2 tests, pour être quasiment certain que le nombre est premier, ca fonctionne à merveille mais seulement pour les petits nombres, pour les gros nombre c'est long, très très long, donc j'ai du mal a comprendre comment les algorithme de génération de clé font pour générer des clé de 2048 bits voir plus en quelques secondes ^^
J'utilise la bibliothèque "InfInt" qui me permet de manipuler de grand nombres.
Pour faire le test de Fermat, j'utilise une fonction puissance que j'ai implémenter pour InfInt (C'est vraiment une fonction naïve, elle calcul bêtement chaque puissance), et pour le modulo, j'utilise simplement "%".

Voila ^^ Je sais pas trop si c'est dû au test de Fermat où peut-être à la possibilité de mieux implémenter la puissance et le modulo.
Merci d'avance !

[yahiko]

A en croire la page Wikipédia de l'algorithme RSA, c'est plutôt le Test de primalité de Miller-Rabin qui est utilisé en pratique dont la complexité peut être ramenée en O(k × (log n)^2), comparativement à la complexité en O(k × (log n)^2 × log log n × log log log n) du Test de primalité de Fermat visiblement plus lent.

[chaa13]

Effectivement, tu as raison, je croyais que c'était seulement celui de Fermat, cependant je crois que les implémentation d'aujourd'hui effectuent plusieurs tests dont celui de Fermat et celui de Miller-Rabin. Enfin bon, la fonction isprime() de Xcas me renvoie presque instantanément la primalité d'un nombre de l'ordre de 10^20. Alors que mon implémentation de Fermat à des difficulté à 10^5 :'D, personnellement j'aimerais bien le finir avec le test de Fermat, mais si vraiment je n'y arrive pas, je passe sur Miller-Rabin ou j'essayerais un test déterministe ^^

[yahiko]

Avec un algo de Fermat ou de Miller-Rabin en JavaScript (qui n'est pas réputé pour ses performances, loin de là), j'obtiens la primalité d'un nombre comme 5600748293801 entre 3 et 5ms.

Je pense que ton problème viens plus de ton implémentation. Peut-être regarder du côté de ta bibliothèque qui gére les grands nombres... En tout cas, sans code, difficile de voir le problème.

[10_GOTO_10]

J'utilise la bibliothèque "InfInt" qui me permet de manipuler de grand nombres.
Pour faire le test de Fermat, j'utilise une fonction puissance que j'ai implémenter pour InfInt (C'est vraiment une fonction naïve, elle calcul bêtement chaque puissance), et pour le modulo, j'utilise simplement "%"

Tu ne peux pas calculer une puissance suivi d'un modulo de façon "naïve" sur des grands nombres : un grand nombre élevé à la puissance un grand nombre, tu vas vite te retrouver avec des nombres ayant un nombre astronomique de chiffres.

Mais heureusement, on peut quand même le calculer en utilisant des astuces de calcul comme l'exponentiation rapide, voir le détail ici:
http://mynath.free.fr/rsa/rsa-expo.php3

[chaa13]

Merci beaucoup !
C'est résolu, l'algorithme de l'exponentiation rapide fonctionne super bien, et j'obtient un résultat directe pour un nombre a 12 chiffres :'D

[Flodelarab]

Bonjour,

Alors que mon implémentation de Fermat à des difficulté à 10^5

Oui, parce que, là, tu avais juste à dresser la liste des nombres premiers avec un crible d'Erathostène... puis la réponse aurait été instantanée