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.
T’as un exemple à me filer ?
[/li]