# include <math.h>
# include <stdio.h>

using namespace std;

# include "fermat_factor.hpp"

//****************************************************************************80

void fermat_factor ( int n, int &f1, int &f2 )

//****************************************************************************80
//
//  Purpose:
//
//    fermat_factor() uses Fermat factorization on an integer.
//
//  Discussion:
//
//    The method determines values A and B such that 
//      N = A^2 - B^2  = ( A + B ) * ( A - B ).
//
//    The method is most efficient when B is small, that is, the two
//    factors are close.  For encryption, the key N is often generated
//    by two primes that are roughly the same size, and this make this
//    method complete more quickly.
//
//  Licensing:
//
//    This code is distributed under the MIT license. 
//
//  Modified:
//
//    10 April 2025
//
//  Author:
//
//    John Burkardt
//
//  Reference:
//
//    Manon Bischoff,
//    This more than 380-year-old trick can crack some modern encryption,
//    Spektrum der Wissenschaft,
//    09 April 2025.
//
//  Input:
//
//    int n: the number to be factored.
//
//  Output:
//
//    int &f1, &f2: factors of n.
//
{
  int n2;
  int n3;
  int n4;

  n2 = floor ( sqrt ( ( double ) ( n ) ) );

  while ( n2 <= n )
  {
    n3 = n2 * n2 - n;
    n4 = floor ( sqrt ( ( double ) ( n3 ) ) );

    if ( n4 * n4 == n3 )
    {
      f1 = n2 + n4;
      f2 = n2 - n4;
      break;
    }
    n2 = n2 + 1;
  }

  return;
}