/*
  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 NTL (ZZ Theory Library di V. Shoup).
*/


#include <NTL/ZZ.h>

/*
  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"
*/

ZZ
pollard(ZZ n, ZZ seed) {

  iterazioni = 0;
  ZZ f = seed;
  ZZ g = seed;
  for (unsigned j = 0; j < max_num_iterazioni; ++j) {
    ++iterazioni;
    f = 1 + f * f;
    f = f % n;
    g = 1 + g * g;
    g = g % n;
    g = 1 + g * g;
    g = g % n;
    ZZ 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(to_ZZ(-1));
}

int main() {

  ZZ n = to_ZZ("6700417");
  n = n * to_ZZ("641");

  ZZ j = pollard(n, to_ZZ(0));

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