Très grand nombres en c++ [Résolu]

pop70 181 Messages postés mardi 6 avril 2010Date d'inscription 7 janvier 2012 Dernière intervention - 28 nov. 2010 à 15:19 - Dernière réponse : cs_Chouchou182 252 Messages postés vendredi 13 juin 2003Date d'inscription 25 avril 2011 Dernière intervention
- 29 nov. 2010 à 09:21
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
Afficher la suite 

4 réponses

Répondre au sujet
cs_Chouchou182 252 Messages postés vendredi 13 juin 2003Date d'inscription 25 avril 2011 Dernière intervention - 28 nov. 2010 à 18:03
+3
Utile
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,
Cette réponse vous a-t-elle aidé ?  
Commenter la réponse de cs_Chouchou182
pop70 181 Messages postés mardi 6 avril 2010Date d'inscription 7 janvier 2012 Dernière intervention - 28 nov. 2010 à 18:37
0
Utile
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
Commenter la réponse de pop70
pop70 181 Messages postés mardi 6 avril 2010Date d'inscription 7 janvier 2012 Dernière intervention - 28 nov. 2010 à 19:23
0
Utile
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
Commenter la réponse de pop70
cs_Chouchou182 252 Messages postés vendredi 13 juin 2003Date d'inscription 25 avril 2011 Dernière intervention - 29 nov. 2010 à 09:21
0
Utile
Salut, chez moi ça marche...

#include <NTL/ZZ.h>

int
main()
{
  NTL::ZZ a, b, c; 

  std::cin >> a; 
  std::cin >> b; 
  c = (a+1)*(b+1);
  std::cout << c << "\n";
  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,
Commenter la réponse de cs_Chouchou182

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.