/*
  Questo programma fa parte di una libreria messa a disposizione dei
  lettori del libro
  Alessandro Languasco & Alessandro Zaccagnini,
  Introduzione alla Crittografia, Ulrico Hoepli Editore, Milano, 2004.

  Scomposizione in fattori primi dell'intero "n":
  Algoritmo rho di Pollard.
  Si veda il Paragrafo 6.5.4 del libro citato.

  NB. Per la compilazione di questo programma è necessario che sia
  installata la libreria CLN (Class Library for Numbers).
*/

#include <cln/cln.h>

using namespace cln;

typedef cl_I Number;

/*
  Variabile per il conteggio del numero di iterazioni necessarie
  (serve per confrontare fra loro i vari algoritmi proposti)
*/
long long unsigned
iterazioni;

/*
  Numero massimo di iterazioni prima di rinunciare al calcolo e
  ricominciarlo con un nuovo valore della variabile "seed".
*/
long long unsigned
max_num_iterazioni = 1000;

/*
  Algoritmo di Pollard per la ricerca di un fattore primo di "n"
  partendo dal valore iniziale "seed"
*/

Number
pollard(Number n, Number seed) {

  iterazioni = 0;
  Number f = seed;
  Number g = seed;
  for (unsigned j = 0; j < max_num_iterazioni; ++j) {
    ++iterazioni;
    f = 1 + f * f;
    f = mod(f, n);
    g = 1 + g * g;
    g = mod(g, n);
    g = 1 + g * g;
    g = mod(g, n);
    Number mcd = gcd(f - g, n);
    if (mcd > 1)
      return(mcd);
  }
  // Se dopo "max_num_iterazioni" iterazioni ancora non si trova un
  // fattore di "n" rinuncia e prova con un "seed" diverso
  return(-1);
}

int main() {

  Number n = 89681;
  n = n * 96079;

  Number j = pollard(n, 0);

  std::cout << "Numero da fattorizzare: " << n << std::endl;
  std::cout << "Fattore: " << j;
  std::cout << "    numero di iterazioni: " << iterazioni << std::endl;
}