DÉCOMPOSITION EN FACTEURS PREMIERS AVEC GMP

Commentaire de pop70 le 28/11/2010 15:45:12

Ouhou ! Ce code est posté pile au bon moment !
Je viens de déposer une question sur le forum pour savoir comment manipuler de très grands nombres, et je trouve la réponse 2mn plus tard (GMP) :)
D'ailleurs si je cherchais de à faire de très grands nombres, c'est pour essayer de faire un petit programme de cryptage RSA expliqué sur un site.
Pour valeur d'exemple il donne un produit de 2 nombres premiers égal à 283189. Puis ils disent que dans la pratique, il faut des nombres bien plus grands, car celui-ci peut-être rapidement décomposé... Il font bien de le dire, j'ai testé ton programme est en moins d'1/10 de seconde il l'a décomposé en 503x563.

Vraiment bravo! Je pense que ce code va m'être bien utile et à beaucoup d'autre aussi.
De plus, il est très bien commenté, et ça facilite grandement la lecture, surtout lorsqu'on ne connait pas encore, comme moi, la librairie GMP.

Encore une fois Merci pgl10 !

Commentaire de pgl10 le 28/11/2010 23:26:37

=> POP70 : merci pour cet aimable commentaire.
=> BACTERIUS : le test de primalité de Miller-Rabin avec gmp est disponible à http://en.literateprograms.org/Miller-Rabin_primality_test_(C,_GMP). Je l'ai compilé. Chez moi, le grand nombre écrit ci-dessus est détecté composite. Je suppose qu'on peut aussi le trouver ailleurs et notamment sur cppfrance avec NTL. Par contre je signale que la publication de ce grand nombre casse la mise en page habituelle de la page Internet Explorer actuelle. J'avais déjà indiqué que mon petit logiciel diviseurs.exe n'était pas fait pour faire un bon test de primalité, comme ceux de Miller-Rabin, de AKS ou d'autres, mais seulement d'exercice pour utiliser gmp. Ceci dit merci pour les remarques pour lesquelles je suis d'accord. Bye, pgl10

Commentaire de pgl10 le 29/11/2010 13:39:44

Merci à Nicolas SOREL (Nix) pour avoir coupé en morceaux le très grand nombre ci-dessus et avoir rétabli la présentation habituelle.
A noter que les tests de primalité exacts ou probabilistes sont bien sûr voisins du sujet traité ici mais en général ils ne font pas la décomposition en facteurs premiers. Ces deux problèmes sont sont complémentaires mais différents.

Commentaire de smaida le 06/12/2010 21:58:50

    * #include <stdio.h>
    * #include <stdlib.h>
    * #include <gmp.h>
    * int main (int argc, char *argv[]) { // décomposition d'un entier n quelconque
    * mpz_t n,i,ii,q; // en produit de nombres premiers
    * unsigned int s,t[]={4,2,4,2,4,6,2,6};
    * mpz_init(n);
    * mpz_init(i);
    * mpz_init(ii);
    * mpz_init(q);
    * // lecture du nombre n à décomposer
    * if(argc==2) gmp_sscanf(argv[1],"%Zd",n);
    * else {
    * input: printf("\nEntrez un nombre entier plus grand que 1 : ");
    * gmp_scanf("%Zd",n);
    * if(mpz_cmp_si(n,2)<0) goto input; // if(n<2) goto input
    * }
    * s=2;
    * // est-ce que s divise n une ou plusieurs fois ?
    * prems : if(mpz_cmp_ui(n,s)==0) goto fin; // si n = s
    * if(mpz_divisible_ui_p(n,s)) { // si s divise n
    * mpz_div_ui(q,n,s); // q = n / s
    * gmp_printf("\n\n %Zd = %Zd * %d",n,q,s);
    * mpz_set(n,q); // n = n / s
    * goto prems;
    * }
    * if(s==2) {s=3; goto prems;}
    * if(s==3) {s=5; goto prems;}
    * s=0;
    * mpz_set_si(i,7); // i = 7
    * mpz_set_si(ii,49); // ii = 49
    * // à partir de i, calcul du plus petit diviseur i de n ( i sera premier )
    * boucle: for(;;) { // pour chaque valeur de i
    * if(mpz_cmp(ii,n)>0) goto fin; // if(i*i>n) : donc n est premier
    * if(mpz_divisible_p(n,i)!=0) { // si i divise n
    * mpz_div(q,n,i); // q = n / i
    * gmp_printf("\n\n %Zd = %Zd * %Zd",n,q,i);
    * mpz_set(n,q); // n = n / i
    * goto boucle;
    * }
    * else { // si i ne divise pas n on devrait prendre pour i le nombre
    * mpz_add_ui(i,i,t[s++]); // premier suivant, mais il n'est pas connu. Donc, on prend
    * if(s==8) s=0; // l'entier suivant en évitant les multiples de 2, 3 et 5
    * mpz_mul(ii,i,i); // ii = i * i
    * }
    * }
    * fin: gmp_printf("\n\n %Zd est premier\n\n\n",n);
    * mpz_clear(n);
    * mpz_clear(i);
    * mpz_clear(ii);
    * mpz_clear(q);
    * system("pause");
    * return 0;
    * }

Commentaire de pgl10 le 18/12/2011 20:19:33

Ccgousset : Je ne connais pas bien les gmpxx.h et gmpxx.lib. J'utilise avec Visual C++ 6.0 la version 4.1.2 de GMP citée dans la description. Cette version vient avec gmp.h et gmp.lib qui n'ont aucun problème de compilation ou de link edit. C'est une version plus ancienne, mais on trouve assez facilement sur Internet des documentations pour cette version. Et mon C++ est en fait principalement du C, les parties spécifiques du C++ ne sont guère utilisées ici. Désolé de ne dire rien de mieux.