# Algo rho de Pollard en C, avec GMP

**URL:** <https://www.debian-fr.org/t/algo-rho-de-pollard-en-c-avec-gmp/26874>\
**Category:** Programmation\
**Created:** [Février 20, 2016, 10:26 UTC](https://www.debian-fr.org/t/algo-rho-de-pollard-en-c-avec-gmp/26874 "2016-02-20T22:26:46Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![Lancazar](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/l/b782af/32.png) [@Lancazar](https://www.debian-fr.org/u/Lancazar)\
**Post date:** [Février 20, 2016, 10:26 UTC](https://www.debian-fr.org/t/algo-rho-de-pollard-en-c-avec-gmp/26874/1 "2016-02-20T22:26:46Z")

</div>

Bonjour,

Je code un petit programme qui doit mettre en pratique l’algorithme rho de Pollard. J’utilise pour ce faire la librairir GMP.

Programme principalement codé par Syam, merci à lui  
Si vous avez un moyen de l’améliorer, n’hésitez pas !

Voici le code en vrac.

[code]#include \<stdio.h\>  
#include \<stdlib.h\>  
#include \<gmp.h\>

void f(mpz\_t, unsigned int, mpz\_t);  
void prho(unsigned int, mpz\_t);

// Global, utilisé pour les comparaisons avec la constante 1  
// On ne peut pas simplement utiliser (mpz\_get\_ui(…) == 1) car :  
// If op is too big to fit an unsigned long then just the least significant bits that do fit are returned.  
// The sign of op is ignored, only the absolute value is used.  
mpz\_t mpz1;

int main(int argc, char\*\* argv)  
{  
FILE\* file;  
mpz\_t n;  
unsigned int i = 1;

if ((argc \< 2) || (argc \> 3) || !(file = fopen(argv[1], “r”)))  
{  
fprintf(stderr, “Usage: prho FICHIER [ENTIER]\n”);  
exit(1);  
}

mpz\_init\_set\_ui(mpz1, 1);  
mpz\_init(n);  
mpz\_inp\_str(n, file, 10);  
fclose(file);  
gmp\_printf(“N = %Zd\n”, n);

if (argc == 3)  
i = atoi(argv[2]);  
prho(i, n);

mpz\_clear(n);  
mpz\_clear(mpz1);  
return 0;  
}

// f(x) = (x^2 + c) mod n, c != 0,-2  
void f(mpz\_t x, unsigned int i, mpz\_t n)  
{  
mpz\_pow\_ui(x, x, 2);  
mpz\_add\_ui(x, x, i);  
mpz\_mod(x, x, n);  
}

// rho de Pollard :  
//  
// Inputs: n, the integer to be factored; and f(x), a pseudo-random function modulo n  
//  
// Output: a non-trivial factor of n, or failure.  
//  
// 1. x ← 2, y ← 2; d ← 1  
// 2. While d = 1:  
// 1. x ← f(x)  
// 2. y ← f(f(y))  
// 3. d ← GCD(|x − y|, n)  
// 3. If d = n, return failure.  
// 4. Else, return d.  
//  
void prho(unsigned int i, mpz\_t n)  
{  
mpz\_t x, y, d, tmp;

mpz\_init\_set\_ui(x, 2);  
mpz\_init\_set\_ui(y, 2);  
mpz\_init\_set\_ui(d, 1);  
mpz\_init(tmp);

while (mpz\_cmp(d, mpz1) == 0)  
{  
// x ← f(x)  
f(x, i, n);  
// y ← f(f(y))  
f(y, i, n);  
f(y, i, n);

```
// d ← GCD(|x − y|, n)
mpz_sub(tmp, x, y);
mpz_abs(tmp, tmp);
mpz_gcd(d, tmp, n);

```

}

mpz\_clear(x);  
mpz\_clear(y);  
mpz\_clear(tmp);

// if there is a factor  
if (mpz\_cmp(d, n) != 0)  
{  
// n := n / d  
mpz\_tdiv\_q(n, n, d);

```
//i + 1 arbitrary chosen evol, 
prho(++i, d);

if (mpz_cmp(n, mpz1) != 0)
  prho(i, n);

```

}  
else  
gmp\_printf("%Zd\n", n);

mpz\_clear(d);  
}[/code]

pour compiler (avec libgmp3-dev d’installé)  
gcc main.c -o prho -lgmp

il faut appeller le programme ainsi  
prho fichiercontenantunentier [unentierautrequezerooudeux]

essayez par exemple avec 8051, 240, 4 … Pour voir les différents résultats. Essayez aussi avec 222119, de cette manière :  
echo 222119 \> ./n  
./prho n  
./prho n 5

Encore et toujours imparfait.

---

<div class="post-metadata">

**Author:** ![syam](https://www.debian-fr.org/user_avatar/www.debian-fr.org/syam/32/2951_2.png) [@syam](https://www.debian-fr.org/u/syam)\
**Post date:** [Février 20, 2016, 10:26 UTC](https://www.debian-fr.org/t/algo-rho-de-pollard-en-c-avec-gmp/26874/2 "2016-02-20T22:26:52Z")

</div>

C’est relativement explicite : tu essayes de faire un modulo zero.  
Pour une raison ou pour une autre, ton n est égal à zéro.

Comme tu appelles f() plusieurs fois de suite, le mpz\_clear(n) est-il bien à sa place dans f() ? M’est avis que non, vu que ni f() ni prho() ne sont propriétaires de cette donnée. Rappelle toi la règle d’or : seul son propriétaire a le droit de libérer une ressource !

Edit : en fait c’est encore pire…

1. main() alloue un n, qui est passé en paramètre à prho()
2. prho() réinitialise ce n, qui est ensuite passé en paramètre à f()
3. f() utilise ce n puis l’efface (f() est appelée 3 fois de suite)
4. récursion 2/3
5. main() efface n

Je connais pas libgmp précisément, mais de toutes façons y’a un gros souci là, faut revoir ton organisation.

---

<div class="post-metadata">

**Author:** ![Lancazar](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/l/b782af/32.png) [@Lancazar](https://www.debian-fr.org/u/Lancazar)\
**Post date:** [Février 20, 2016, 10:26 UTC](https://www.debian-fr.org/t/algo-rho-de-pollard-en-c-avec-gmp/26874/3 "2016-02-20T22:26:54Z")

</div>

Je suis d’accord pour dire que c’est en bordel… Mais l’occurence, à chaque fois que je créé un mpz\_t, il a une nouvelle adresse et n’est accessible qu’en local de mes instructions non ? Donc même si je nomme plusieurs n, ce n’est jamais le même qui est appelé ?

C’est pourquoi d’ailleurs j’utilise le c++, puisque pour f(x), je ne peux pas initialiser et faire un clear sur les valeurs GMP enregistrées : j’agit donc directement sur ce qui m’est donné en argument.

Bon, je nettois tout ça, un peu de rigueur ne peut de toute façon pas faire de mal.

edit : nettoyé : chaque nom de variable est unique. Je passe toujours les adresses des variables GMP, elles sont toutes ainsi initialisée une fois et supprimée avant de quitter le programme.

Mais ça ne change rien : floating point exception.

GDB :

code r n  
Starting program: /home/xkth/prog/crypto/pRho/prho n  
N=%

Program received signal SIGFPE, Arithmetic exception.  
0x00007ffff7b8b99e in \_\_gmp\_exception () from /usr/lib/libgmp.so.3  
(gdb) bt  
#0 0x00007ffff7b8b99e in \_\_gmp\_exception () from /usr/lib/libgmp.so.3  
#1 0x00007ffff7b8b9be in \_\_gmp\_divide\_by\_zero () from /usr/lib/libgmp.so.3  
#2 0x00007ffff7ba73b0 in \_\_gmpz\_tdiv\_r () from /usr/lib/libgmp.so.3  
#3 0x00007ffff7ba059b in \_\_gmpz\_mod () from /usr/lib/libgmp.so.3  
#4 0x0000000000400da0 in p(\_\_mpz\_struct (&) [1], unsigned int, \_\_mpz\_struct (&) [1]) ()  
#5 0x0000000000400e2e in prho(unsigned int, \_\_mpz\_struct (&) [1]) ()  
#6 0x0000000000400f60 in prho(unsigned int, \_\_mpz\_struct (&) [1]) ()  
#7 0x0000000000400d35 in main ()[/code]

Ceci fait, le problème est bien l’initialisation de n donc… même en faisant ainsi :  
mpz\_init(n);  
mpz\_set\_ui(n,atol(argv[1]));  
gmp\_printf(“N=%Z\n”,n);

Qui semble être la base pour initialiser une telle variable, n est totalement vide. même pas à 0 donc, ce que devrait faire mpz\_init(); .

Il doit y avoir un truc ultra simple qui m’échappe.

---

<div class="post-metadata">

**Author:** ![syam](https://www.debian-fr.org/user_avatar/www.debian-fr.org/syam/32/2951_2.png) [@syam](https://www.debian-fr.org/u/syam)\
**Post date:** [Février 20, 2016, 10:26 UTC](https://www.debian-fr.org/t/algo-rho-de-pollard-en-c-avec-gmp/26874/4 "2016-02-20T22:26:55Z")

</div>

> [@Lancazar](#):
>
> à chaque fois que je créé un mpz\_t, il a une nouvelle adresse et n’est accessible qu’en local de mes instructions non ? Donc même si je nomme plusieurs n, ce n’est jamais le même qui est appelé ?

Techniquement, lors d’un passage de paramètre par valeur tu copies effectivement la structure (mpz\_t). Mais en pratique, cette structure contient… un pointeur vers les données réelles. Donc, même quand tu passes ça par valeur tu ne travailles pas sur une copie.

Je n’ai pas encore regardé en détail la nouvelle version avec passage par référence, je m’y atèle de ce pas.  
Edit : ah ben non, je sais pas à quoi ressemble le fichier que tu lis. 😊 T’as un exemple à me filer ?

---

<div class="post-metadata">

**Author:** ![Lancazar](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/l/b782af/32.png) [@Lancazar](https://www.debian-fr.org/u/Lancazar)\
**Post date:** [Février 20, 2016, 10:26 UTC](https://www.debian-fr.org/t/algo-rho-de-pollard-en-c-avec-gmp/26874/5 "2016-02-20T22:26:55Z")

</div>

très simple :

5468

dans un fichier texte, par exemple “n”. Puis ./prho n

---

<div class="post-metadata">

**Author:** ![Lancazar](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/l/b782af/32.png) [@Lancazar](https://www.debian-fr.org/u/Lancazar)\
**Post date:** [Février 20, 2016, 10:27 UTC](https://www.debian-fr.org/t/algo-rho-de-pollard-en-c-avec-gmp/26874/6 "2016-02-20T22:27:44Z")

</div>

J’up pour demander simplement ce qui cloche avec ça :

[code]#include \<gmp.h\>

int main(int argc, char\*\* argv){  
mpz\_t n;

mpz\_init(n);  
mpz\_set\_ui(n,12);  
gmp\_printf(“N=%Z\n”,n);

mpz\_clear(n);  
return 0;  
}[/code]

On ne peut pas faire plus simple, et pourtant la seule sortie que j’ai est N=%…

Quelqu’un pourrait m’expliquer pourquoi ?

---

<div class="post-metadata">

**Author:** ![syam](https://www.debian-fr.org/user_avatar/www.debian-fr.org/syam/32/2951_2.png) [@syam](https://www.debian-fr.org/u/syam)\
**Post date:** [Février 20, 2016, 10:28 UTC](https://www.debian-fr.org/t/algo-rho-de-pollard-en-c-avec-gmp/26874/7 "2016-02-20T22:28:48Z")

</div>

Pour gmp\_printf, il faut indiquer également ce qu’ils appellent la “conversion” en plus du type de nombre GMP :

```auto

```

Voir : [gmplib.org/manual/Formatted-Outp … ut-Strings](http://gmplib.org/manual/Formatted-Output-Strings.html#Formatted-Output-Strings)

Pour les autres problèmes dans ton code, déjà j’arrive pas à piger le but de ton implémentation, y’a trop de trucs qui diffèrent par rapport à l’algo théorique (notamment la récursion). Qu’est-ce que tu as essayé de faire en introduisant ces modifs, précisément ?

---

<div class="post-metadata">

**Author:** ![Lancazar](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/l/b782af/32.png) [@Lancazar](https://www.debian-fr.org/u/Lancazar)\
**Post date:** [Février 20, 2016, 10:29 UTC](https://www.debian-fr.org/t/algo-rho-de-pollard-en-c-avec-gmp/26874/8 "2016-02-20T22:29:18Z")

</div>

J’essayais de donner tous les facteurs de N, pas seulement l’un d’entre eux.  
Tant que j’aurais pas inclus des tests plus élaborés, je laisse la version qui ne donne qu’un facteur.

merci pour m’avoir mis les nez sur les erreurs bêtes que j’ai fais.

---

<div class="post-metadata">

**Author:** ![syam](https://www.debian-fr.org/user_avatar/www.debian-fr.org/syam/32/2951_2.png) [@syam](https://www.debian-fr.org/u/syam)\
**Post date:** [Février 20, 2016, 10:29 UTC](https://www.debian-fr.org/t/algo-rho-de-pollard-en-c-avec-gmp/26874/9 "2016-02-20T22:29:24Z")

</div>

Bon, j’ai un truc qui marche apparemment bien. En vrac, quelques remarques par rapport à ton code d’origine (avant que tu ne supprimes la récursion)…

[ul][li] LE gros bug venait de la récursion : tu prenais le reste de la division (n mod d) au lieu du quotient (mpz\_tdiv), et tu faisais l’appel récursif au mauvais endroit (la récursion ne doit avoir lieu que si on a trouvé un facteur).[/li]  
[li] Pas besoin de passer les paramètres par référence, puisque la structure mpz\_t est faite de telle manière que son passage en paramètre par copie ait le même effet qu’un passage par référence.[/li]  
[li] mpz\_get\_ui() n’est pas sûr, il tronque le résultat si le nombre est trop grand (à priori ça n’avait pas d’incidence pour les valeurs que tu manipulais vu qu’elles étaient petites, mais dans l’absolu c’était un bug). Il vaut mieux créer une constante de type mpz\_t qui servira pour les comparaisons avec la valeur 1.[/li]  
[li] Aucun souci pour utiliser des noms de variables identiques dans diverses fonctions, le compilateur ne se mélange pas les pinceaux et c’est plus simple si les noms dans le code correspondent aux noms dans l’algo. 😉[/li]  
[li] Sinon, j’ai juste simplifié un peu ton code, et aussi rajouté une deuxième récursion pour essayer de décomposer un facteur en ses facteurs premiers. Le souci étant qu’il n’y a aucune garantie que les facteurs trouvés soient des facteurs premiers. Mis à part ce détail ça semble fonctionner.[/li][/ul]

[code]#include \<stdio.h\>  
#include \<stdlib.h\>  
#include \<gmp.h\>

void f(mpz\_t, unsigned int, mpz\_t);  
void prho(unsigned int, mpz\_t);

// Global, utilisé pour les comparaisons avec la constante 1  
// On ne peut pas simplement utiliser (mpz\_get\_ui(…) == 1) car :  
// If op is too big to fit an unsigned long then just the least significant bits that do fit are returned.  
// The sign of op is ignored, only the absolute value is used.  
// Autrement dit, risque de collision pour les grands nombres.  
mpz\_t mpz1;

int main(int argc, char\*\* argv)  
{  
FILE\* file;  
mpz\_t n;  
unsigned int i = 1;

mpz\_init\_set\_ui(mpz1, 1);

if ((argc \< 2) || (argc \> 3) || !(file = fopen(argv[1], “r”)))  
{  
fprintf(stderr, “Usage: prho FICHIER [ENTIER]\n”);  
exit(1);  
}

mpz\_init(n);  
mpz\_inp\_str(n, file, 10);  
fclose(file);  
gmp\_printf(“N = %Zd\n”, n);

if (argc == 3)  
i = atoi(argv[2]);  
prho(i, n);

mpz\_clear(n);  
mpz\_clear(mpz1);  
return 0;  
}

// f(x) = (x^2 + c) mod n, c != 0,-2  
void f(mpz\_t x, unsigned int i, mpz\_t n)  
{  
mpz\_pow\_ui(x, x, 2);  
mpz\_add\_ui(x, x, i);  
mpz\_mod(x, x, n);  
}

// rho de Pollard :  
//  
// Inputs: n, the integer to be factored; and f(x), a pseudo-random function modulo n  
//  
// Output: a non-trivial factor of n, or failure.  
//  
// 1. x ← 2, y ← 2; d ← 1  
// 2. While d = 1:  
// 1. x ← f(x)  
// 2. y ← f(f(y))  
// 3. d ← GCD(|x − y|, n)  
// 3. If d = n, return failure.  
// 4. Else, return d.  
//  
void prho(unsigned int i, mpz\_t n)  
{  
mpz\_t x, y, d, tmp;

mpz\_init\_set\_ui(x, 2);  
mpz\_init\_set\_ui(y, 2);  
mpz\_init\_set\_ui(d, 1);  
mpz\_init(tmp);

while (mpz\_cmp(d, mpz1) == 0)  
{  
// x ← f(x)  
f(x, i, n);  
// y ← f(f(y))  
f(y, i, n);  
f(y, i, n);

```
// d ← GCD(|x − y|, n)
mpz_sub(tmp, x, y);
mpz_abs(tmp, tmp);
mpz_gcd(d, tmp, n);

```

}

// on efface x, y et tmp avant la récursion  
// ils ne sont plus utilisés, inutile qu’ils occupent des ressources  
// pendant le reste des calculs, qui peut être assez long  
mpz\_clear(x);  
mpz\_clear(y);  
mpz\_clear(tmp);

// si on trouve un facteur…  
if (mpz\_cmp(d, n) != 0)  
{  
// on prend le quotient, pas le reste !!  
// accessoirement, on effectue cette opération AVANT que la récursion  
// sur “d” ne modifie ce dernier  
mpz\_tdiv\_q(n, n, d);

```
// on essaye de trouver les facteurs premiers du facteur juste trouvé
// le choix (i + 2) est totalement arbitraire et devrait être amélioré
// (aucune assurance que "d" soit totalement décomposé en facteurs premiers)
// si on conserve simplement "i" sans modification, le facteur ne sera jamais décomposé plus avant
prho(i + 2, d);

if (mpz_cmp(n, mpz1) != 0)
  prho(i, n);

```

}  
else  
// on affiche “n” lorsqu’on n’a trouvé aucun facteur  
// sachant que lorsqu’on trouve un facteur, à la fois ce facteur et le quotient  
// sont décomposés récursivement, ça signifie que TOUS les facteurs  
// non-décomposables vont passer par ce chemin et donc être affichés  
gmp\_printf(“F = %Zd\n”, n);

mpz\_clear(d);  
}[/code]

---

<div class="post-metadata">

**Author:** ![Lancazar](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/l/b782af/32.png) [@Lancazar](https://www.debian-fr.org/u/Lancazar)\
**Post date:** [Février 20, 2016, 10:29 UTC](https://www.debian-fr.org/t/algo-rho-de-pollard-en-c-avec-gmp/26874/10 "2016-02-20T22:29:28Z")

</div>

Super, merci… C’est du bon sens.

C’est intéressant le fait de pouvoir élaborer des structures de manière à pouvoir copier les valeurs sans les passer en référence. Merci de l’avoir pointé du doigt.

J’écris désormais le p-1, qui n’est pas non plus très compliqué, je prendrais en compte toutes tes remarques (dumoins j’essaierais :).

---

<div class="post-metadata">

**Author:** ![syam](https://www.debian-fr.org/user_avatar/www.debian-fr.org/syam/32/2951_2.png) [@syam](https://www.debian-fr.org/u/syam)\
**Post date:** [Février 20, 2016, 10:29 UTC](https://www.debian-fr.org/t/algo-rho-de-pollard-en-c-avec-gmp/26874/11 "2016-02-20T22:29:29Z")

</div>

> [@Lancazar](#):
>
> C’est intéressant le fait de pouvoir élaborer des structures de manière à pouvoir copier les valeurs sans les passer en référence.

C’est une ruse de sioux en C : on déclare un typedef en tant que tableau (à un seul élément) de la structure concernée, et du coup le passage en paramètre se fait systématiquement par pointeur (puisqu’il s’agit d’un tableau). Pour accéder aux membres, il suffit d’utiliser la notation pointeur var-\>membre au lieu de la notation var.membre habituelle pour une structure pile (on pourrait aussi utiliser un index de tableau var[0].membre, ça correspondrait plus à la réalité mais le code serait moins lisible).

[code]#include \<stdio.h\>

struct ref\_struct  
{  
int i;  
};  
typedef struct ref\_struct ref\_t[1];  
// ou, plus concis (si on n’a pas besoin de la structure en elle-même) :  
// typedef struct  
// {  
// int i;  
// }  
// ref\_t[1];

void f(ref\_t r)  
{  
++r-\>i;  
}

int main()  
{  
ref\_t r;  
r-\>i = 1;  
f(r);  
printf(«&nbsp;%d\n&nbsp;», r-\>i);  
return 0;  
}[/code]  
😉

---

<div class="post-metadata">

**Author:** ![Lancazar](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/l/b782af/32.png) [@Lancazar](https://www.debian-fr.org/u/Lancazar)\
**Post date:** [Février 20, 2016, 10:29 UTC](https://www.debian-fr.org/t/algo-rho-de-pollard-en-c-avec-gmp/26874/12 "2016-02-20T22:29:34Z")

</div>

Super !

Plus qu’à mettre en pratique pour que ça rentre…

---

<div class="post-metadata">

**Author:** ![Lancazar](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/l/b782af/32.png) [@Lancazar](https://www.debian-fr.org/u/Lancazar)\
**Post date:** [Février 21, 2016, 12:15 UTC](https://www.debian-fr.org/t/algo-rho-de-pollard-en-c-avec-gmp/26874/13 "2016-02-21T00:15:01Z")

</div>

Je passe rapidement pour mettre à jour le topic…

J’ai trouvé un nombre qui fait planter le programme  
253199530752162813639052871138083720574153437161394896249854561312828455598591162347792026599

j’implémente un test de primalité pour passer outre, et terminer normalement.  
Selon le test de Miller-Rabin, celui-ci est sûrement premier.

Outre Miller-Rabin, qui me semble le plus approprié, quelqu’un aurait des idées d’implémentation intéressantes ?