très grand nombres en c++Résolu

Question

Bonjour, j'essaie actuellement de faire un petit programme de cryptage basé sur le principe du RSA, seulement pour cela il faut manipuler des très grands nombres. Après quelques recherches j'ai trouvé le type int64_t qui code sur 64 bits. Mais j'en suis au cryptage et déjà se pose un problème :

lors de : NombreCrypté = Nombre^E (mod N)  (le plus important quoi )

J'ai essayé : 

int64_t NOMBRE_CRYPTE =  (int64_t)(pow((int64_t)NOMBRE, (int64_t)E)) % (int64_t) N ;

Mais j'ai l'impression que le résultat dépasse 64 bits (ou en tout cas quelque chose foire ), car quelque soit le nombre, j'obtient le même résultat pour le nombre crypté.

De plus, dans ce cas ça ne me gène pas trop parce que c'est juste pour tester, mais je crois savoir que 64 bits et trop petit pour un algorithme RSA, car il est trop vite décrypté. 

Donc j'aimerais savoir si vous avez une idée du problème, s'il vient de mon calcul, ou du type des variables et si c'est du type, comment faire...

Voilà, Merci d'avance   


Pop70

cs_Chouchou182 · Accepted Answer

Salut,
Pour la manipulation de grands nombres (de taille arbitraire) en C++, tu peux utiliser la NTL (et sa classe ZZ ou ZZ_p) :
NTL is a high-performance, portable C++ library providing data structures and algorithms for manipulating signed, arbitrary length integers, and for vectors, matrices, and polynomials over the integers and over finite fields.(http://www.shoup.net/ntl/)

À propos de ton exemple, la fonction pow que je connais travaille sur des double, ce qui est mauvais dans ton cas: tu veux un calcul exact sur des entier et pas une approximation via les flottants.

Bonne prog,

pop70 · Answer

Merci, je venais de voir aussi la librairie GMP, mais impossible de l'installer, trop d'erreurs (dommage)... Bref toujours dans un souci d'installation j'ai téléchargé la bibliothèque NTL 5.5.2 pour Windows d'après le lien que tu m'as donné, et je me retrouve avec ces dossiers :

C:\Program Files\CodeBlocks\WinNTL-5_5_2 qui contient :

-doc
-GetTime
-include 
-MakeDesc
-misc
-src
-test

Dans aucun des dossiers je n'ai de .dll ou .lib, comment fais-je pour installer la libraire dans CodeBlock et la linker, qui pour l'instant, quand j'écris :  #include <NTL/ZZ.h> , ne connais pas ?

(J'ai bien vu la documentation, mais il faut dire, qu'a mon grand regret, je n'ai pas un excellent niveau en anglais, surtout sur des termes techniques...) 

Pop70

pop70 · Answer

J'ai réussi à linker le dossier include dans search directory/Compiler, sans rien déplacer et ça marche à un détaille près : je n'arrive pas à faire un cout<< ou un cin>> de mes valeurs, est-ce que c'est parce qu'il manque encore des fichier à linker ? Pop70

cs_Chouchou182 · Answer

Salut, chez moi ça marche... #include int main() { NTL::ZZ a, b, c; std::cin >> a; std::cin >> b; c = (a+1)*(b+1); std::cout << c << " "; return 0; } Sans rien lier d'autre que la ntl (enfin, en tous cas je ne le demande pas explicitement). g++ -lntl ... Qu'est-ce que ça dit chez toi ? Presque hors sujet: concernant les soucis d'installation, tu peux mettre sur un coin de disque dur une distribution à la Ubuntu et puis: apt-get install libntl-dev et ça marche ! Bonne prog,

Très grand nombres en c++

4 réponses

Votre réponse

Discussions similaires