Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Euler's factorization method
open-in-new
<h2 id="disadvantage-and-limitation">Disadvantage and limitation</h2> <p>The great disadvantage of Euler's factorization method is that it cannot be applied to factoring an integer with any prime factor of the form 4<i>k</i> + 3 occurring to an odd power in its prime factorization, as such a number can never be the sum of two squares. Even odd <a href="/facts/Composite_number/SPtW9ftC">composite numbers</a> of the form 4<i>k</i> + 1 are often the product of two primes of the form 4<i>k</i> + 3 (e.g. 3053 = 43 × 71) and again cannot be factored by Euler's method. </p><p>This restricted applicability has made Euler's factorization method disfavoured for <a href="/facts/Computer/SQe1aK05">computer</a> factoring <a href="/facts/Algorithm/fnl5NmRt">algorithms</a>, since any user attempting to factor a random integer is unlikely to know whether Euler's method can actually be applied to the integer in question. It is only relatively recently that there have been attempts to develop Euler's method into computer algorithms for use on specialised numbers where it is known Euler's method can be applied. </p> <h2 id="theoretical-basis">Theoretical basis</h2> <p>The <a href="/facts/Brahmagupta%25E2%2580%2593Fibonacci_identity/brCDr0Rn">Brahmagupta–Fibonacci identity</a> states that the product of two sums of two squares is a sum of two squares. Euler's method relies on this theorem but it can be viewed as the converse, given n = a 2 + b 2 = c 2 + d 2 {\displaystyle n=a^{2}+b^{2}=c^{2}+d^{2}} we find n {\displaystyle n} as a product of sums of two squares. </p><p>First deduce that </p> a 2 − c 2 = d 2 − b 2 {\displaystyle a^{2}-c^{2}=d^{2}-b^{2}} <p>and factor both sides to get </p> ( a − c ) ( a + c ) = ( d − b ) ( d + b ) {\displaystyle (a-c)(a+c)=(d-b)(d+b)} (1) <p>Now let k = gcd ( a − c , d − b ) {\displaystyle k=\operatorname {gcd} (a-c,d-b)} and h = gcd ( a + c , d + b ) {\displaystyle h=\operatorname {gcd} (a+c,d+b)} so that there exists some constants l , m , l ′ , m ′ {\displaystyle l,m,l',m'} satisfying </p> <ul><li> ( a − c ) = k l {\displaystyle (a-c)=kl} ,</li> <li> ( d − b ) = k m {\displaystyle (d-b)=km} ,</li></ul> <p> gcd ( l , m ) = 1 {\displaystyle \operatorname {gcd} (l,m)=1} </p> <ul><li> ( a + c ) = h m ′ {\displaystyle (a+c)=hm'} ,</li> <li> ( d + b ) = h l ′ {\displaystyle (d+b)=hl'} ,</li></ul> <p> gcd ( l ′ , m ′ ) = 1 {\displaystyle \operatorname {gcd} (l',m')=1} </p><p>Substituting these into equation (1) gives </p> k l h m ′ = k m h l ′ {\displaystyle klhm'=kmhl'} <p>Canceling common factors yields </p> l m ′ = l ′ m {\displaystyle lm'=l'm} <p>Now using the fact that ( l , m ) {\displaystyle (l,m)} and ( l ′ , m ′ ) {\displaystyle \left(l',m'\right)} are pairs of relatively prime numbers, we find that </p> <ul><li> l = l ′ {\displaystyle l=l'} </li> <li> m = m ′ {\displaystyle m=m'} </li></ul> <p>So </p> <ul><li> ( a − c ) = k l {\displaystyle (a-c)=kl} </li> <li> ( d − b ) = k m {\displaystyle (d-b)=km} </li> <li> ( a + c ) = h m {\displaystyle (a+c)=hm} </li> <li> ( d + b ) = h l {\displaystyle (d+b)=hl} </li></ul> <p>We now see that m = gcd ( a + c , d − b ) {\displaystyle m=\operatorname {gcd} (a+c,d-b)} and l = gcd ( a − c , d + b ) {\displaystyle l=\operatorname {gcd} (a-c,d+b)} </p><p>Applying the <a href="/facts/Brahmagupta%25E2%2580%2593Fibonacci_identity/brCDr0Rn">Brahmagupta–Fibonacci identity</a> we get </p> ( k 2 + h 2 ) ( l 2 + m 2 ) = ( k l + h m ) 2 + ( k m − h l ) 2 = ( ( a − c ) + ( a + c ) ) 2 + ( ( d − b ) − ( d + b ) ) 2 = ( 2 a ) 2 + ( 2 b ) 2 = 4 n . {\displaystyle \left(k^{2}+h^{2}\right)\left(l^{2}+m^{2}\right)=(kl+hm)^{2}+(km-hl)^{2}={\bigl (}(a-c)+(a+c){\bigr )}^{2}+{\bigl (}(d-b)-(d+b){\bigr )}^{2}=(2a)^{2}+(2b)^{2}=4n.} <p>As each factor is a sum of two squares, one of these must contain both even numbers: either ( k , h ) {\displaystyle (k,h)} or ( l , m ) {\displaystyle (l,m)} . Without loss of generality, assume that pair ( k , h ) {\displaystyle (k,h)} is even. The factorization then becomes </p> n = ( ( k 2 ) 2 + ( h 2 ) 2 ) ( l 2 + m 2 ) . {\displaystyle n=\left(\left({\tfrac {k}{2}}\right)^{2}+\left({\tfrac {h}{2}}\right)^{2}\right)\left(l^{2}+m^{2}\right).\,} <h2 id="worked-example">Worked example</h2> <p>Since: 1000009 = 1000 2 + 3 2 = 972 2 + 235 2 {\displaystyle \ 1000009=1000^{2}+3^{2}=972^{2}+235^{2}} </p><p>we have from the formula above: </p> <table><tbody><tr><td><i>a</i> = 1000</td><td>(A) <i>a</i> − <i>c</i> = 28</td><td><i>k</i> = gcd[A,C] = 4</td></tr><tr><td><i>b</i> = 3</td><td>(B) <i>a</i> + <i>c</i> = 1972</td><td><i>h</i> = gcd[B,D] = 34</td></tr><tr><td><i>c</i> = 972</td><td>(C) <i>d</i> − <i>b</i> = 232</td><td><i>l</i> = gcd[A,D] = 14</td></tr><tr><td><i>d</i> = 235</td><td>(D) <i>d</i> + <i>b</i> = 238</td><td><i>m</i> = gcd[B,C] = 116</td></tr></tbody></table> <p>Thus, </p> 1000009 = [ ( 4 2 ) 2 + ( 34 2 ) 2 ] ⋅ [ ( 14 2 ) 2 + ( 116 2 ) 2 ] {\displaystyle 1000009=\left[\left({\frac {4}{2}}\right)^{2}+\left({\frac {34}{2}}\right)^{2}\right]\cdot \left[\left({\frac {14}{2}}\right)^{2}+\left({\frac {116}{2}}\right)^{2}\right]\,} = ( 2 2 + 17 2 ) ⋅ ( 7 2 + 58 2 ) {\displaystyle =\left(2^{2}+17^{2}\right)\cdot \left(7^{2}+58^{2}\right)\,} = ( 4 + 289 ) ⋅ ( 49 + 3364 ) {\displaystyle =(4+289)\cdot (49+3364)\,} = 293 ⋅ 3413 {\displaystyle =293\cdot 3413\,} <h2 id="pseudocode">Pseudocode</h2> function Euler_factorize(int n) -> list[int] if is_prime(n) then print("Number is not factorable") exit function for-loop from a=1 to a=ceiling(sqrt(n)) b2 = n - a*a b = floor(sqrt(b2)) if b*b==b2 break loop preserving a,b if a*a+b*b!=n then print("Failed to find any expression for n as sum of squares") exit function for-loop from c=a+1 to c=ceiling(sqrt(n)) d2 = n - c*c d = floor(sqrt(d2)) if d*d==d2 then break loop preserving c,d if c*c+d*d!=n then print("Failed to find a second expression for n as sum of squares") exit function A = c-a, B = c+a C = b-d, D = b+d k = GCD(A,C)//2, h = GCD(B,D)//2 l = GCD(A,D)//2, m = GCD(B,C)//2 factor1 = k*k + h*h factor2 = l*l + m*m return list[ factor1, factor2 ] <ul><li>Ore, Oystein (1988). <a href="https://archive.org/details/numbertheoryitsh0000orey/page/59">"Euler's Factorization Method"</a>. <i>Number Theory and Its History</i>. Courier Corporation. pp. <a href="https://archive.org/details/numbertheoryitsh0000orey/page/59">59–64</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-486-65620-5.</li> <li>McKee, James (1996). "Turning Euler's Factoring Method into a Factoring Algorithm". <i>Bulletin of the London Mathematical Society</i>. 4 (28): 351–355. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1112%2Fblms%2F28.4.351">10.1112/blms/28.4.351</a>.</li></ul>