Fermat's factorization method

Fermat's factorization method, named after <a href="/facts/Pierre_de_Fermat/FLbUh75u">Pierre de Fermat</a>, is based on the representation of an <a href="/facts/Even_and_odd_numbers/7zq2UM4V">odd</a> <a href="/facts/Integer/PUwwrawx">integer</a> as the <a href="/facts/Difference_of_two_squares/3gkVr71S">difference of two squares</a>:

N
        =
        
          a
          
            2
          
        
        −
        
          b
          
            2
          
        
        .
      
    
    {\displaystyle N=a^{2}-b^{2}.}

That difference is <a href="/facts/Algebra/nMdqczjo">algebraically</a> factorable as 
 
 
 
 (
 a
 +
 b
 )
 (
 a
 −
 b
 )
 
 
 {\displaystyle (a+b)(a-b)}
 
; if neither factor equals one, it is a proper factorization of N.
Each odd number has such a representation. Indeed, if 
 
 
 
 N
 =
 c
 d
 
 
 {\displaystyle N=cd}
 
 is a factorization of N, then

N
        =
        
          
            (
            
              
                
                  c
                  +
                  d
                
                2
              
            
            )
          
          
            2
          
        
        −
        
          
            (
            
              
                
                  c
                  −
                  d
                
                2
              
            
            )
          
          
            2
          
        
        .
      
    
    {\displaystyle N=\left({\frac {c+d}{2}}\right)^{2}-\left({\frac {c-d}{2}}\right)^{2}.}

Since N is odd, then c and d are also odd, so those halves are integers. (A multiple of four is also a difference of squares: let c and d be even.)
In its simplest form, Fermat's method might be even slower than trial division (worst case). Nonetheless, the combination of trial division and Fermat's is more effective than either by itself.

Fermat's factorization method open-in-new

Fermat's factorization method