/*
  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 di Fermat.
  Si veda il Paragrafo 6.5.2 del libro citato.
*/

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include "aritmetica.cc"

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

/*
  Fattorizzazione di Fermat (senza il miglioramento di Lehman);
  si cerca di decomporre "n" come differenza di due quadrati:
  "n = x^2 - y^2".
  La funzione resituisce "mcd(x - y, n)" che è un fattore (non
  necessariamente primo) di "n".
*/

long long int
fermat(long long int n) {

  iterazioni = 0;
  // Lavoriamo solo con numeri positivi
  if (n < 0)
    n *= -1;

  int alpha = 0;
  // Rimuoviamo eventuali potenze di 2 da "n"
  while ((n % 2) == 0) {
    ++alpha;
    n /= 2;
  }
  if (alpha > 0) {
    std::cout << "Rimosso un fattore 2^" << alpha;
    std::cout << " prima di iniziare l'algoritmo di Fermat" << std::endl;
  }

  // La funzione "radice_quadrata()" restituisce la radice quadrata
  // intera approssimata per difetto, ed è definita in
  // "aritmetica.cc"
  long long int x = radice_quadrata(n);
  bool test = true;
  // Ripetiamo il ciclo seguente fino a trovare un valore di "x" per
  // cui "x^2 - n" sia un quadrato perfetto.
  // NB. Un tale valore esiste sicuramente: infatti basta prendere
  // "x = (n+1)/2", e quindi il ciclo si interrompe prima o poi.
  // È in questo punto che è necessario che "n" sia dispari.
  long long int y = 0;
  while (test) {
    ++x;
    ++iterazioni;
    long long int xq = x * x;
    long long int yq = xq - n;
    y = radice_quadrata(yq);
    if (y * y == yq)
      test = false;
  }
  return mcd(x - y, n);
}

int
main() {

  // Come numero di prova usiamo il "numero di Jevons" definito a p. 175
  long long int n = 8616460799LL;

  std::cout <<"Fattorizzazione alla Fermat di " << n << std::endl;
  long long int m = fermat(n);
  std::cout << "Trovato il fattore " << m << std::endl;
  std::cout << "Sono state necessarie " << iterazioni << " iterazioni";
  std::cout << std::endl;

}