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:


Lo que nos llevarà a obtener un factor de n calculando el Máximo Común Divisor entre b^M-1 y 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;
}