Cryptage RSA, problème pour x^y mod zRésolu

Question

Bonjour, j'étudie le C en cours depuis un mois (à raison de 2h par semaine, c'est à dire, trop peu je pense ! ), et j'ai un programme à faire qui réalise un cryptage RSA, puis un décryptage, ceci n'est pas le réel problème. En fait, mon programme tourne (pour le moment je n'ai fait que le cryptage) sauf sur un point, et l'un des plus important, quand il doit faire x^b mod n, avec de gros nombres, par exemple pour l'exposant, on s'attend à ce que cela pose problème, j'ai donc fait une fonction utilisant l'algorithme des carrés et des multiplications pour ne pas être géné sur ce point, et pourtant elle ne fonctionne pas avec de trop gros nombres (J'ai essayé avec 16^32 mod 77, aucun problème, par contre avec 25199^28549 mod 94631, le programme n'affiche pas le bon résultat, et même un nombre négatif : -43965 ! J'ai tout d'abord pensé que le problème venait de la taille de mes variables, des int, mais je ne peux pas utiliser de modulo sur autre chose que des entiers, apparement, donc je ne vois pas comment résoudre ce problème si c'est ça. voici ici ma fonction :

int puis(int x, int y, int z)
{   
    int res = 1;
    while (y > 0)
    {
          if (y%2==1)
          {
                    res = ((res*x)%z);
                    y = y - 1;
          }
          else
          {
                    x = ((x*x)%z);
                    y = y/2;
          }
    }
    return(res);
                    
}

Je pourrais poster le programme entier si nécessaire.
Merci de votre lecture, et des réponses que vous pourrez m'apporter.

Shuu

cs_rt15 · Accepted Answer

Bienvenue,

Une réponse rapide...

Les int c'est codé sur 32 bits (Sauf cas rare), et c'est signé, donc ça permet de compter jusqu'à 2147483647.

Le type entier à peu près supporté, c'est le __int64 (Ou un typedef de ce type), qui permettent de compter jusqu'à 9223372036854775807.

Par contre, les processeurs actuels ne sont moins bon avec les __int64 qu'avec les int (Y compris les AMD64 qui font tourner un Windows 32bits... Et les Windows 64 bits se font plutôt rares !) -> Perte de performances.

Si tu as pas mal de temps, tu peux éventuellement regarder du côté de MMX et des SSE, qui sont des extensions au processeurs destinés aux calculs mathématiques. MMX est très répandu, et SSE l'est aussi mais pas forcément en dernière version.

Shuugeki · Answer

Merci beaucoup pour ces informations plus qu'enrichissantes, mais si j'ai bien compris alors, je ne peux pas faire fonctionner mon programme avec de trop grandes puissances / modulo ?

cs_rt15 · Answer

Bin les capacités du processeur sont effectivement limitées... Si tu mets 2147483647 dans un int et que tu ajoute 2, ça te fais un drôle de résultat...

Il faut faire des codes plus complexes pour aller au delà, par exemple en utilisant la librairie Bignum.

BruNews · Answer

__int64 est ce que produit à tout coup un cpu depuis le 386 (32 bits) pour une multiplication de 2 INT32.

mul ecx
Resultat en EDX:EAX donc 64 bits.

ciao...
BruNews, MVP VC++

Cryptage RSA, problème pour x^y mod z

4 réponses

Votre réponse

Discussions similaires