Aller au menu - Aller au contenu

Icône Comment utiliser GMP ?

L'auteur de ce cours cherche un repreneur pour continuer son travail
Parfois, certains auteurs de cours n'ont plus le temps de rédiger et de mettre à jour leur travail. Ils recherchent alors un nouvel auteur pour "reprendre" leur tutoriel (voir la liste des tutoriels en attente de repreneur).
Contactez l'auteur si vous aimeriez continuer la rédaction !

Par Avatar Simon Chabot (TuxWeb) et Avatar Toulousaing
Mise à jour : 09/09/2009
Difficulté : Intermédiaire Intermédiaire Creative Commons BY-SA
1 105 visites depuis 7 jours, dont 45 sur ce chapitre classé 112/786
Maintenant que nous avons installé et vérifié que la bibliothèque GMP était fonctionnelle, nous pouvons apprendre à nous en servir !
Retour en haut
Sommaire du chapitre :
Icône du chapitre
Chapitre précédent Sommaire
Retour en haut

L'objet mpz_class

La bibliothèque GMP permet de gérer de grands nombres ; elle a donc son propre type de variables (d'objet, plus précisément) ; mpz_class qui va nous permettre d'utiliser simplement les opérateurs arithmétiques usuels (+, -, *, /) avec nos grands nombres. Voyons ensemble comment on se sert de ce nouvel objet !

Code : C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <iostream>
#include <gmpxx.h>

int main (int argc, char **argv)
{
   std::string nombre("35");

   mpz_class a(16), b(nombre), c;

   std::cout << "le nombre a vaut : " << a << std::endl;
   std::cout << "le nombre b vaut : " << b << std::endl;
   std::cout << "le nombre c vaut : " << c << std::endl;

  return 0;
}

En compilant ce code, on obtient ceci :

Code : Console
le nombre a vaut : 16
le nombre b vaut : 35
le nombre c vaut : 0


On commence donc par inclure la bibliothèque GMP (ligne 2). On peut ensuite créer nos objets. Je vous présente ici 3 façons distinctes de créer un objet (ligne 8).


    

  • En indiquant par un entier (long) la valeur désirée (objet "a")
    • 

  • En indiquant par une chaine (string) la valeur désirée (objet "b")
    • 

  • En indiquant aucune valeur (objet "c")
    • 




On pourra noter le fait que lorsque la construction d'un objet mpz_class, si on a omis de préciser une valeur (comme pour l'objet "c"), GMP l'initialise à zéro.




Je ne serais pas plus long sur la création des objets mpz_class, l'essentiel à savoir est vu.

                

                
Retour en haut

            
                

                    

                        Les opérateurs usuels
                        
                    


                    
Sommes, différences, produits, quotients.




Comme vous le savez (normalement !), le C++ offre un concept qui s'appelle la surcharge des opérateurs. L'objet mpz_class nous en fait donc profiter. Je vais être assez rapide sur le sujet, car il n'y a pas vraiment de différence d'utilisation entre les variables de type primitif (long, int, double, etc...) et l'objet mpz_class. Je vais juste vous montrer quelques exemples.



Code : C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <gmpxx.h>

int main (int argc, char **argv)
{
   mpz_class a(16), b(15), c;

   c = a + b;

   std::cout << "a + b = " << c << std::endl;

   c = a - b ; 

   std::cout << "a - b = " << c << std::endl;

   c = a * b ; 

   std::cout << "a * b = " << c << std::endl;

   c = a / b ; 

   std::cout << "a / b = " << c << std::endl;


   return 0;
}







Une fois compilé, on obtient un résultat facilement prévisible :



Code : Console
a + b = 31
a - b = 1
a * b = 240
a / b = 1



Ein ? 16/15 = 1 ? Eh oui, mpz_class ne gère pas les nombres à virgule. (Pour utiliser des virgules, il faut se servir de "mpf_class" (le "f" pour float)). Ceci dit ; mpz_class offre une alternative assez intéressante à cette lacune, chose que nous allons voir tout de suite.





Les divisions




GMP nous donne tout un panel de fonctions sur la division. (Vous trouverez la liste exhaustive à la partie 5.6 de la documentation officielle (dont je vous ai fourni le lien, dans la conclusion du chapitre précédent.)) Voici les prototypes des trois fonctions sur la division qui me semblent primordiaux.


    

  • void mpz_fdiv_q (mpz_t q, mpz_t n, mpz_t d )

    • 

  • void mpz_fdiv_r (mpz_t r, mpz_t n, mpz_t d )

    • 

  • void mpz_fdiv_qr (mpz_t q, mpz_t r, mpz_t n, mpz_t d )

    • 





En voyant ces prototypes, plusieurs questions devraient vous venir à l'esprit :


    

  • Pourquoi utilise-t-on des fonctions, et non des méthodes ?
    • 

  • "mpz_t ? Une nouveau type ? Un nouvel objet ?  :euh: 
    • 

  • A quoi vont bien pouvoir nous servir ces fonctions ?
    • 



Alors, prenons les questions dans l'ordre.


    

  • Il faut savoir, qu'à l'origine, GMP est en C, et non en C++. Certaines fonctions ont été implémentées en C++, des objets (mpz_class ; mpf_class ; mpq_class (nous ne verrons pas ce dernier)) ont été créés pour l'occasion. Cependant, toute la bibliothèque n'a pas basculé en C++, c'est pourquoi il subsiste encore des fonctions telles que ces trois-là.
    • 

  • "mpz_t" découle du fait que la bibliothèque était à l'origine en C. Il s'agit d'un des trois types de variables créés à l'origine de la GMP.
    • 

  • Ces trois fonctions ont chacune leur propre rôle :
    

      

    •  La première permet d'obtenir le quotient de la division euclidienne de "n" par "d".
      • 

    •  La deuxième permet d'obtenir le reste de la division euclidienne de "n" par "d".
      • 

    •  Et la dernière permet d'obtenir le quotient et le reste de la division euclidienne de "n" par "d".
      • 

    • 





Maintenant que l'on sait à quoi servent ces fonctions, et que l'on sait pourquoi le prototype utilise des "mpz_t" et non des "mpz_class", on va voir comment on les utilise. Pour s'en servir, il va falloir que l'on "transforme" notre objet "mpz_class" en une variable du type "mpz_t". C'est pour cela que la méthoque get_mpz_t() a vu le jour !



Je ne fais l'exemple que d'une fonction, les autres, vous pourrez les tester vous même : c'est le même principe.



Code : C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <iostream>
#include <gmpxx.h>

int main (int argc, char **argv)
{
   mpz_class dividende(35), diviseur(15), quotient, reste;

   mpz_fdiv_qr(quotient.get_mpz_t(), reste.get_mpz_t(), 
                  dividende.get_mpz_t(), diviseur.get_mpz_t());

   std::cout << dividende << " = " << quotient << " x " << diviseur ;
   std::cout << " + " << reste << std::endl;

   return 0;
}





Ce qui nous donne le résultat suivant : 



Code : Console
35 = 2 x 15 + 5

                

                
Retour en haut

            
                

                    

                        Quelques fonctions mathématiques...
                        
                    


                    
La bibliothèque GMP est, certes, une bibliothèque qui sait gérer les très grands nombres, mais avant tout, elle est une bibliothèque mathématique. C'est pour cela qu'elle regorge de fonctions mathématiques. Certaines sont les mêmes que celles disponibles dans la bibliothèque mathématique standard. (Ceil(), floor(), sqrt(), abs(), etc.) Ce n'est pas sur celles-ci que je veux appuyer, car leur utilisation est assez intuitive et nous ne nous en servirons pas durant ce tutoriel. Nous allons voir ensemble seulement les fonctions dont nous ferons usage plus tard.




La fonction "modulo"




Vous vous en rappelez de cette fonction ? On l'a vue dans la partie théorique du tutoriel. C'est sur cette fonction que repose, quasiment, tout le système RSA.



Je vous donne juste le prototype, avec l'exemple vu avant (pour la division) vous devriez vous en sortir...  :p 




void mpz_mod (mpz_t r, mpz_t n, mpz_t d )





Cette fonction effectue le calcul suivant : r = n mod(d)




Vous noterez que les fonctions mpz_mod et mpz_fdiv_r font le même travail ; cela dit, nous voulons le modulo, alors autant utiliser la fonction prévue à cet effet...





La fonction "puissance"




La fonction "puissance" est aussi une des fonctions à la base du système RSA. 

Voici son prototype :




void mpz_pow_ui (mpz_t rop, mpz_t base, unsigned long int exp )





Cette fonction effectue le calcul suivant : rop = baseexp




L'exposant doit être un entier de type "unsigned long int", et non un "mpz_class" !



La méthode get_ui() permet de transformer un mpz_class en "unsigned long int" ; cependant, attention à vérifier que votre objet loge dans "unsigned long int" !









Une fonction idéale pour RSA !




Nous pourrions très bien faire notre programme RSA en utilisant seulement les deux dernières fonctions que l'on vient de voir. Cependant, calculer une puissance puis un modulo (l'un après l'autre) demande de nombreux calculs, et donc du temps. L'astuce consiste en fait à calculer le modulo et la puissance en même temps !  :-° . Et grâce à un algorithme et un peu de magie mathématique ( :magicien: ), on gagne du temps ! 



Voici le prototype de la fonction "RSA" :




void mpz_powm (mpz_t rop, mpz_t base, mpz_t exp, mpz_t modulo )





Cette fonction effectue le calcul suivant : rop = baseexp mod (modulo)



Vous l'aurez deviné ; c'est cette fonction qui va nous servir lors du chiffrage et du déchiffrage de nos messages secrets.



                

                
Retour en haut

            


Voilà, je pense que les présentations de bases sont désormais faites.



A vous de manipuler les objets mpz_class (et pourquoi pas mpf_class, si vous désirez travailler avec des flottants).



Au prochain chapitre, nous attaquons les choses sérieuses ! La création du programme commencera... :soleil:



    

        
            
            
        
    


    

        
            

                

                    
                    
                    
                

            

        
            Chapitre précédent
        
            Sommaire
        
    







    
Retour en haut



    
Partager

    


    


    

    
Retour en haut

    
            

                3 commentaires pour "Comment utiliser GMP ?"
                

                    Note moyenne :
                        3.71
                    / 4
                    (31 votes)
                    
                

            

        
        

            
              

                Pseudo
                Commentaire
              

            
            
              
                

                  
                    
                      Hors ligne 
                    
                      Pole
                    
                  
                  
                    #
                    
                         Posté le 17/12/2008 à 10:47:34
                    
                    
                


                
                    

                
                
                    

Chieur professionnel
Avatar



    





                		
                
                    
                    "Cependant, calculer un modulo, puis une puissance (l'un après l'autre)"

Plutôt l'inverse ...
                    
                        
Les caisses sont vides

Traité européen de 1965 :

Citation : Traité


FONCTIONNAIRES ET AGENTS DES COMMUNAUTÉS EUROPÉENNES

Article 12

Sur le territoire de chacun des États membres et quelle que soit leur nationalité, les fonctionnaires et autres agents des Communautés:

a) jouissent de l'immunité de juridiction pour les actes accomplis par eux, y compris leurs paroles et écrits, en leur qualité officielle, sous réserve de l'application des dispositions des traités relatives, d'une part, aux règles de la responsabilité des fonctionnaires et agents envers les Communautés et, d'autre part, à la compétence de la Cour pour statuer sur les litiges entre les Communautés et leurs fonctionnaires et autres agents. Ils continueront à bénéficier de cette immunité après la cessation de leurs fonctions,






                        
 

                    
                		
                

              
                

                  
                    
                      Hors ligne 
                    
                      sylvior
                    
                  
                  
                    #
                    
                         Posté le 07/10/2009 à 08:10:19
                    
                    
                


                
                    

                
                
                    




     Ville : Saint marcel

	Pays : France métropolitaine
 Études : INSA Lyon






                		
                
                    
                    je copie le premier main que tu donne, je tente de compiler et il me trouve des erreurs dans la bibliothèque. je sais pas quoi faire j'ai pourtant bien compilé la bibliothèque, il m'a sorti aucune erreur pendant la compilation et elle est bien dans le dossier include de MinGW. Je comprends pas pourquoi il ne veut pas me compiler

edit : en fait sa venait de ce con de windows qui avait pas donné les droits en lecture du fichier

Sinon très bon tuto sur le RSA, j'ai bien compris le principe même si il reste quelques imprécisions c'est normal c'est le siteduzero
                    
                		
                

              
                

                  
                    
                      Hors ligne 
                    
                      mazzel
                    
                  
                  
                    #
                    
                         Posté le 08/03/2012 à 22:10:02
                    
                    
                


                
                    

                
                
                    

Avatar

    

    Avis : Très bon
        
    



    





                		
                
                    
                    j'adore pas j'aime
                    
                
                

              
            
        

        
            
Voir tous les commentaires