Fermat's factorization method

<h2 id="basic-method">Basic method</h2>
<p>One tries various values of <i>a</i>, hoping that 
  
    
      
        
          a
          
            2
          
        
        −
        N
        =
        
          b
          
            2
          
        
      
    
    {\displaystyle a^{2}-N=b^{2}}
  
, a square.
</p>
FermatFactor(N): <i>// N should be odd</i>
    a ← ceiling(sqrt(N))
    b2 ← a*a - N
    repeat until b2 is a square:
        a ← a + 1
        b2 ← a*a - N 
     // equivalently: 
     // b2 ← b2 + 2*a + 1<i> </i>
     // a ← a + 1
    return a - sqrt(b2) <i>// or a + sqrt(b2)</i>

<p>For example, to factor 
  
    
      
        N
        =
        5959
      
    
    {\displaystyle N=5959}
  
, the first try for <i>a</i> is the square root of 5959 rounded up to the next integer, which is 78. Then 
  
    
      
        
          b
          
            2
          
        
        =
        
          78
          
            2
          
        
        −
        5959
        =
        125
      
    
    {\displaystyle b^{2}=78^{2}-5959=125}
  
. Since 125 is not a square, a second try is made by increasing the value of <i>a</i> by 1.  The second attempt also fails, because 282 is again not a square.
</p>
<table><tbody><tr><th>Try:</th><td>1</td><td>2</td><td>3</td></tr><tr><th><i>a</i></th><td>78</td><td>79</td><td>80</td></tr><tr><th><i>b</i>2</th><td>125</td><td>282</td><td>441</td></tr><tr><th><i>b</i></th><td>11.18</td><td>16.79</td><td>21</td></tr></tbody></table>
<p>The third try produces the perfect square of 441. Thus, 
  
    
      
        a
        =
        80
      
    
    {\displaystyle a=80}
  
, 
  
    
      
        b
        =
        21
      
    
    {\displaystyle b=21}
  
, and the factors of 5959 are 
  
    
      
        a
        −
        b
        =
        59
      
    
    {\displaystyle a-b=59}
  
 and 
  
    
      
        a
        +
        b
        =
        101
      
    
    {\displaystyle a+b=101}
  
.
</p><p>Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of <i>a</i> and <i>b</i>. That is, 
  
    
      
        a
        +
        b
      
    
    {\displaystyle a+b}
  
 is the smallest factor ≥ the square-root of <i>N</i>, and so 
  
    
      
        a
        −
        b
        =
        N
        
          /
        
        (
        a
        +
        b
        )
      
    
    {\displaystyle a-b=N/(a+b)}
  
 is the largest factor ≤ root-<i>N</i>. If the procedure finds 
  
    
      
        N
        =
        1
        ⋅
        N
      
    
    {\displaystyle N=1\cdot N}
  
, that shows that <i>N</i> is prime.
</p><p>For 
  
    
      
        N
        =
        c
        d
      
    
    {\displaystyle N=cd}
  
, let <i>c</i> be the largest subroot factor. 
  
    
      
        a
        =
        (
        c
        +
        d
        )
        
          /
        
        2
      
    
    {\displaystyle a=(c+d)/2}
  
, so the number of steps is approximately 
  
    
      
        (
        c
        +
        d
        )
        
          /
        
        2
        −
        
          
            N
          
        
        =
        (
        
          
            d
          
        
        −
        
          
            c
          
        
        
          )
          
            2
          
        
        
          /
        
        2
        =
        (
        
          
            N
          
        
        −
        c
        
          )
          
            2
          
        
        
          /
        
        2
        c
      
    
    {\displaystyle (c+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2=({\sqrt {N}}-c)^{2}/2c}
  
.
</p><p>If <i>N</i> is prime (so that 
  
    
      
        c
        =
        1
      
    
    {\displaystyle c=1}
  
), one needs 
  
    
      
        O
        (
        N
        )
      
    
    {\displaystyle O(N)}
  
 steps. This is a bad way to prove primality. But if <i>N</i> has a factor close to its square root, the method works quickly. More precisely, if <i>c</i> differs less than 
  
    
      
        
          
            
              (
              
                4
                N
              
              )
            
          
          
            1
            
              /
            
            4
          
        
      
    
    {\displaystyle {\left(4N\right)}^{1/4}}
  
 from 
  
    
      
        
          
            N
          
        
      
    
    {\displaystyle {\sqrt {N}}}
  
, the method requires only one step; this is independent of the size of <i>N</i>.
</p>
<h2 id="fermats-and-trial-division">Fermat's and trial division</h2>
<p>Consider trying to factor the prime number <i>N</i> = 2,345,678,917, but also compute <i>b</i> and <i>a</i> − <i>b</i> throughout.  Going up from 
  
    
      
        
          
            N
          
        
      
    
    {\displaystyle {\sqrt {N}}}
  
 rounded up to the next integer, which is 48,433, we can tabulate:
</p>
<table><tbody><tr><th>Try</th><td>1st</td><td>2nd</td><td>3rd</td><td>4th</td></tr><tr><th><i>a</i></th><td>48,433</td><td>48,434</td><td>48,435</td><td>48,436</td></tr><tr><th><i>b</i>2</th><td>76,572</td><td>173,439</td><td>270,308</td><td>367,179</td></tr><tr><th><i>b</i></th><td>276.7</td><td>416.5</td><td>519.9</td><td>605.9</td></tr><tr><th><i>a</i> − <i>b</i></th><td>48,156.3</td><td>48,017.5</td><td>47,915.1</td><td>47,830.1</td></tr></tbody></table>
<p>In practice, one wouldn't bother with that last row until <i>b</i> is an integer. But observe that if <i>N</i> had a subroot factor above 
  
    
      
        a
        −
        b
        =
        47830.1
      
    
    {\displaystyle a-b=47830.1}
  
, Fermat's method would have found it already.
</p><p>Trial division would normally try up to 48,432; but after only four Fermat steps, we need only divide up to 47830, to find a factor or prove primality.
</p><p>This all suggests a combined factoring method. Choose some bound 
  
    
      
        
          a
          
            
              m
              a
              x
            
          
        
        >
        
          
            N
          
        
      
    
    {\displaystyle a_{\mathrm {max} }>{\sqrt {N}}}
  
; use Fermat's method for factors between 
  
    
      
        
          
            N
          
        
      
    
    {\displaystyle {\sqrt {N}}}
  
 and 
  
    
      
        
          a
          
            
              m
              a
              x
            
          
        
      
    
    {\displaystyle a_{\mathrm {max} }}
  
.  This gives a bound for trial division which is 
  
    
      
        
          a
          
            
              m
              a
              x
            
          
        
        −
        
          
            
              a
              
                
                  m
                  a
                  x
                
              
              
                2
              
            
            −
            N
          
        
      
    
    {\displaystyle a_{\mathrm {max} }-{\sqrt {a_{\mathrm {max} }^{2}-N}}}
  
.  In the above example, with 
  
    
      
        
          a
          
            
              m
              a
              x
            
          
        
        =
        48436
      
    
    {\displaystyle a_{\mathrm {max} }=48436}
  
 the bound for trial division is 47830.  A reasonable choice could be 
  
    
      
        
          a
          
            
              m
              a
              x
            
          
        
        =
        55000
      
    
    {\displaystyle a_{\mathrm {max} }=55000}
  
 giving a bound of 28937.
</p><p>In this regard, Fermat's method gives diminishing returns. One would surely stop before this point:
</p>
<table><tbody><tr><th><i>a</i></th><td>60,001</td><td>60,002</td></tr><tr><th><i>b</i>2</th><td>1,254,441,084</td><td>1,254,561,087</td></tr><tr><th><i>b</i></th><td>35,418.1</td><td>35,419.8</td></tr><tr><th><i>a</i> − <i>b</i></th><td>24,582.9</td><td>24,582.2</td></tr></tbody></table>
<h2 id="sieve-improvement">Sieve improvement</h2>
<p>When considering the table for 
  
    
      
        N
        =
        2345678917
      
    
    {\displaystyle N=2345678917}
  
, one can quickly tell that none of the values of 
  
    
      
        
          b
          
            2
          
        
      
    
    {\displaystyle b^{2}}
  
 are squares:
</p>
<table><tbody><tr><th><i>a</i></th><td>48,433</td><td>48,434</td><td>48,435</td><td>48,436</td></tr><tr><th><i>b</i>2</th><td>76,572</td><td>173,439</td><td>270,308</td><td>367,179</td></tr><tr><th><i>b</i></th><td>276.7</td><td>416.5</td><td>519.9</td><td>605.9</td></tr></tbody></table>
<p>It is not necessary to compute all the square-roots of 
  
    
      
        
          a
          
            2
          
        
        −
        N
      
    
    {\displaystyle a^{2}-N}
  
, nor even examine all the values for a. Squares are always congruent to 0, 1, 4, 5, 9, 16 <a href="/facts/Modular_arithmetic/0wtRa5dU">modulo</a> 20. The values repeat with each increase of a by 10.  In this example, N is 17 mod 20, so subtracting 17 mod 20 (or adding 3), 
  
    
      
        
          a
          
            2
          
        
        −
        N
      
    
    {\displaystyle a^{2}-N}
  
 produces 3, 4, 7, 8, 12, and 19 modulo 20 for these values.  It is apparent that only the 4 from this list can be a square.  Thus, 
  
    
      
        
          a
          
            2
          
        
      
    
    {\displaystyle a^{2}}
  
 must be 1 mod 20, which means that a is 1, 9, 11 or 19 mod 20; it will produce a 
  
    
      
        
          b
          
            2
          
        
      
    
    {\displaystyle b^{2}}
  
 which ends in 4 mod 20 and, if  square, b will end in 2 or 8 mod 10.
</p><p>This can be performed with any modulus. Using the same 
  
    
      
        N
        =
        2345678917
      
    
    {\displaystyle N=2345678917}
  
,
</p>
<table><tbody><tr><td>modulo 16:</td><td>Squares are</td><td>0, 1, 4, or 9</td></tr><tr><td></td><td>N mod 16 is</td><td>5</td></tr><tr><td></td><td>so                               a                      2                                {\displaystyle a^{2}}   can only be</td><td>9</td></tr><tr><td></td><td>and a must be</td><td>3 or 5 or 11 or 13 modulo 16</td></tr><tr><td>modulo 9:</td><td>Squares are</td><td>0, 1, 4, or 7</td></tr><tr><td></td><td>N mod 9 is</td><td>7</td></tr><tr><td></td><td>so                               a                      2                                {\displaystyle a^{2}}   can only be</td><td>7</td></tr><tr><td></td><td>and a must be</td><td>4 or 5 modulo 9</td></tr></tbody></table>
<p>One generally chooses a power of a different prime for each modulus.
</p><p>Given a sequence of <i>a</i>-values (start, end, and step) and a modulus, one can proceed thus:
</p>
FermatSieve(N, astart, aend, astep, modulus)
    a ← astart
    do modulus times:
        b2 ← a*a - N
        if b2 is a square, modulo modulus:
            FermatSieve(N, a, aend, astep * modulus, NextModulus)
        endif
        a ← a + astep
    enddo

<p>But the <a href="/facts/Recursion_(computer_science)/2uXo18Gv">recursion</a> is stopped when few <i>a</i>-values remain; that is, when (aend-astart)/astep is small. Also, because <i>a'</i>s step-size is constant, one can compute successive b2's with additions.
</p>
<h2 id="multiplier-improvement">Multiplier improvement</h2>
<p>Fermat's method works best when there is a factor near the square-root of <i>N</i>.
</p><p>If the approximate ratio of two factors (
  
    
      
        d
        
          /
        
        c
      
    
    {\displaystyle d/c}
  
) is known, then a <a href="/facts/Rational_number/VJQmyY05">rational number</a> 
  
    
      
        v
        
          /
        
        u
      
    
    {\displaystyle v/u}
  
 can be picked near that value. 
  
    
      
        N
        u
        v
        =
        c
        v
        ⋅
        d
        u
      
    
    {\displaystyle Nuv=cv\cdot du}
  
, and Fermat's method, applied to <i>Nuv</i>, will find the factors 
  
    
      
        c
        v
      
    
    {\displaystyle cv}
  
 and 
  
    
      
        d
        u
      
    
    {\displaystyle du}
  
 quickly. Then 
  
    
      
        gcd
        (
        N
        ,
        c
        v
        )
        =
        c
      
    
    {\displaystyle \gcd(N,cv)=c}
  
 and 
  
    
      
        gcd
        (
        N
        ,
        d
        u
        )
        =
        d
      
    
    {\displaystyle \gcd(N,du)=d}
  
. (Unless <i>c</i> divides <i>u</i> or <i>d</i> divides <i>v</i>.)
</p><p>Generally, if the ratio is not known, various 
  
    
      
        u
        
          /
        
        v
      
    
    {\displaystyle u/v}
  
 values can be tried, and try to factor each resulting <i>Nuv</i>. R. Lehman devised a systematic way to do this, so that Fermat's plus trial division can factor N in 
  
    
      
        O
        (
        
          N
          
            1
            
              /
            
            3
          
        
        )
      
    
    {\displaystyle O(N^{1/3})}
  
 time.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p>
<h2 id="other-improvements">Other improvements</h2>
<p>The fundamental ideas of Fermat's factorization method are the basis of the <a href="/facts/Quadratic_sieve/xDrfU9xl">quadratic sieve</a> and <a href="/facts/General_number_field_sieve/elC06ARC">general number field sieve</a>, the best-known algorithms for factoring large <a href="/facts/Semiprimes/J5cNFs7T">semiprimes</a>, which are the "worst-case". The primary improvement that quadratic sieve makes over Fermat's factorization method is that instead of simply finding a square in the sequence of 
  
    
      
        
          a
          
            2
          
        
        −
        n
      
    
    {\displaystyle a^{2}-n}
  
, it finds a subset of elements of this sequence whose <i>product</i> is a square, and it does this in a highly efficient manner. The end result is the same: a difference of squares mod <i>n</i> that, if nontrivial, can be used to factor <i>n</i>.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Completing_the_square/SN6xA8sc">Completing the square</a></li>
<li><a href="/facts/Factorization_of_polynomials/1S9HRKcI">Factorization of polynomials</a></li>
<li><a href="/facts/Factor_theorem/ldVjrt80">Factor theorem</a></li>
<li><a href="/facts/FOIL_rule/msWFgH3h">FOIL rule</a></li>
<li><a href="/facts/Monoid_factorisation/XeHmleRj">Monoid factorisation</a></li>
<li><a href="/facts/Pascal%27s_triangle/tb6BKXbc">Pascal's triangle</a></li>
<li><a href="/facts/Prime_factor/L20FLkgn">Prime factor</a></li>
<li><a href="/facts/Factorization/tXrBXFh1">Factorization</a></li>
<li><a href="/facts/Euler%27s_factorization_method/y3p3WuTs">Euler's factorization method</a></li>
<li><a href="/facts/Integer_factorization/EjMCTz2t">Integer factorization</a></li>
<li><a href="/facts/Program_synthesis/IK3gcrfp">Program synthesis</a></li>
<li><a href="/facts/Table_of_Gaussian_integer_factorizations/hV9n3zTm">Table of Gaussian integer factorizations</a></li>
<li><a href="/facts/Unique_factorization_domain/aYsX2swC">Unique factorization</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Fermat (1894), <i>Oeuvres de Fermat</i>, vol. 2, p. 256</li>
<li>McKee, J (1999). <a href="https://www.ams.org/mcom/1999-68-228/S0025-5718-99-01133-3/home.html">"Speeding Fermat's factoring method"</a>. <i>Mathematics of Computation</i>. 68 (228): 1729–1737. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1090%2FS0025-5718-99-01133-3">10.1090/S0025-5718-99-01133-3</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://kadinumberprops.blogspot.in/2012/11/fermats-factorization-running-time.html">Fermat's factorization running time</a>, at blogspot.in</li>
<li><a href="https://windowspros.ru/projects/fermat-factorization-online-calculator/">Fermat's Factorization Online Calculator</a>, at windowspros.ru</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Lehman, R. Sherman (1974). "Factoring Large Integers" (PDF). Mathematics of Computation. 28 (126): 637–646. doi:10.2307/2005940. JSTOR 2005940. <a href="https://www.ams.org/journals/mcom/1974-28-126/S0025-5718-1974-0340163-2/S0025-5718-1974-0340163-2.pdf" target="_blank">https://www.ams.org/journals/mcom/1974-28-126/S0025-5718-1974-0340163-2/S0025-5718-1974-0340163-2.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Fermat's factorization method open-in-new

Fermat's factorization method