subroutine fermat_factor ( n, f1, f2 )

!*****************************************************************************80
!
!! fermat_factor() uses Fermat factorization on an odd composite 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.
!
  implicit none

  integer f1
  integer f2
  integer n
  integer n2
  integer n3
  integer n4

  n2 = floor ( sqrt ( real ( n ) ) )

  do while ( n2 <= n )

    n3 = n2 * n2 - n
    n4 = floor ( sqrt ( real ( n3 ) ) )

    if ( n4 * n4 == n3 ) then
      f1 = n2 + n4
      f2 = n2 - n4
      exit
    end if

    n2 = n2 + 1

  end do

  return
end