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

/******************************************************************************/

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

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

    09 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:

    integer n: the number to be factored.

  Output:

    integer 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;
}