DÉCOMPOSITION EN FACTEURS PREMIERS AVEC GMP
pop70
Messages postés
181
Date d'inscription
mardi 6 avril 2010
Statut
Membre
Dernière intervention
7 janvier 2012
-
28 nov. 2010 à 15:45
ccgousset Messages postés 150 Date d'inscription samedi 1 août 2009 Statut Membre Dernière intervention 4 mars 2023 - 19 déc. 2011 à 12:46
ccgousset Messages postés 150 Date d'inscription samedi 1 août 2009 Statut Membre Dernière intervention 4 mars 2023 - 19 déc. 2011 à 12:46
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/52531-decomposition-en-facteurs-premiers-avec-gmp
https://codes-sources.commentcamarche.net/source/52531-decomposition-en-facteurs-premiers-avec-gmp
19 déc. 2011 à 12:46
18 déc. 2011 à 20:19
17 déc. 2011 à 23:18
6 déc. 2010 à 21:58
* #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;
* }
29 nov. 2010 à 17:41
29 nov. 2010 à 13:39
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.
28 nov. 2010 à 23:30
Encore une fois je ne critiquais pas ton code mais je te proposais des idées dans la continuité de ce source, c'est tout :p
Cordialement, Bacterius !
28 nov. 2010 à 23:26
=> 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
28 nov. 2010 à 22:50
13506641086599522334960321627880 596993888147560566702752448 514385152651060485953383394028715 0571909441798207282164471 5513736804197039641917430 46496589274256239341020864383202110 37295872576235850964311056407350150818 75106765946292055636855294752135 008528794163773285339061097505 44334999811150056977236890927563
Ce que je suggère à Pgl10 est d'essayer d'implémenter à présent le test de primalité de Miller-Rabin avec gmp (assez simple), et ensuite pour un vrai challengé tenter d'implémenter le crible quadratique : http://fr.wikipedia.org/wiki/Crible_quadratique. C'est juste une suggestion évidemment mais ça donne un bon défi très satisfaisant quand on l'atteint.
Cordialement, Bacterius !
28 nov. 2010 à 15:45
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 !