Factorización III: P-1 de Pollard

Continuamos la serie de artículos sobre factorización con un algoritmo muy sencillo conocido como P-1 de Pollard.

El algoritmo de factorización P-1 de Pollard parte de la idea de smoothness o suavidad. Un número se considera B-smooth cuando todos sus factores son más pequeños que B. Esta idea, puede ser usada con éxito como herramienta de factorización, usando como base el Teorema Pequeño de Fermat:

b^p = b mod p
b^(p-1) = 1 mod p

A partir de la formula anterior deducimos que b^(p-1) - 1 es múltiplo de p. De manera que si disponemos de un número n=pq el cual deseamos factorizar , podremos hacerlo si somos capaces de calcular b^(p-1).
Inicialmente, esto puede parecer complicado, dado que no conocemos p. Pero supongamos que p-1 es B-smooth, para un valor de B bastante pequeño. Esto significaría que podemos calcular un valor M que contenga todos los factores de p-1, por ejemplo, calculando B!. Y si p-1 es un divisor de M, podemos aplicar el Teorema Pequeño de Fermat de la siguiente manera:

b^M = 1 mod p

Lo que nos llevarà a obtener un factor de n calculando el Máximo Común Divisor entre b^M-1 y n.

MCD(b^M-1, n)

Para finalizar, adjunto un programa en C y un ejemplo de su uso.

$ gcc pollard_pm1.c -lgmp -o pollard_pm1
$ ./a.out 97231944203 10
Factor = 888799
Factor = 109397

/* Pollard P-1 */
#include <stdio.h>
#include <gmp.h>


int main(int argc, char *argv[])
{
mpz_t n, a, GCD, tmp, k;
unsigned long int b;
gmp_randstate_t state;

if(argc!=3)
{
printf("Usage: %s [n] [B]\n", argv[0]);
return 0;
}

mpz_init(n);
mpz_init(tmp);
mpz_init(a);
mpz_init(GCD);
mpz_init(k);

mpz_set_str(n, argv[1], 10);
b = atof(argv[2]);

if(mpz_perfect_power_p(n) != 0)
{
mpz_sqrt(tmp, n);
gmp_printf("factor: %Zd\n", tmp);
return 0;
}
mpz_sub_ui(tmp, n, 1);
mpz_fac_ui(k, b);

gmp_randinit_default(state);

while(1)
{
mpz_sub_ui(tmp, n, 1);
mpz_urandomm(a, state, tmp);

if (mpz_cmp_ui(a, 1) <= 0)
mpz_set_ui(a, 2);

mpz_powm(tmp, a, k, n);
mpz_sub_ui(tmp, tmp, 1);
mpz_abs(tmp, tmp);
mpz_gcd(GCD, tmp, n);

if (mpz_cmp_ui(GCD, 1) > 0)
{
if (mpz_probab_prime_p(GCD, 10) > 0)
{
gmp_printf("Factor = %Zd\n", GCD);
mpz_div(n, n, GCD);
}
}
if (mpz_cmp_ui(n, 1) == 0)
{
mpz_clear(a);
mpz_clear(GCD);
mpz_clear(tmp);
mpz_clear(n);
mpz_clear(k);
return 0;
}

if (mpz_probab_prime_p(n, 10) > 0)
{
gmp_printf("Factor = %Zd\n", n);
mpz_clear(a);
mpz_clear(GCD);
mpz_clear(tmp);
mpz_clear(n);
mpz_clear(k);
return 0;
}
}

return 0;
}