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

Messages postés
181
Date d'inscription
mardi 6 avril 2010
Dernière intervention
7 janvier 2012
- - Dernière réponse : cs_Chouchou182
Messages postés
252
Date d'inscription
vendredi 13 juin 2003
Dernière intervention
25 avril 2011
- 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 

Votre réponse

4 réponses

Meilleure réponse
Messages postés
252
Date d'inscription
vendredi 13 juin 2003
Dernière intervention
25 avril 2011
3
Merci
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,

Merci cs_Chouchou182 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources a aidé 98 internautes ce mois-ci

Commenter la réponse de cs_Chouchou182
Messages postés
181
Date d'inscription
mardi 6 avril 2010
Dernière intervention
7 janvier 2012
0
Merci
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
Messages postés
181
Date d'inscription
mardi 6 avril 2010
Dernière intervention
7 janvier 2012
0
Merci
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
Messages postés
252
Date d'inscription
vendredi 13 juin 2003
Dernière intervention
25 avril 2011
0
Merci
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.