歐拉因式分解法

歐拉因式分解法是一種整數分解方法，重點是用兩種方式把要分解的數表示為兩數平方和。比如要分解 ${\displaystyle 1000009}$，這個數既能寫成 ${\displaystyle 1000^{2}+3^{2}}$，又能寫成 ${\displaystyle 972^{2}+235^{2}}$，那麼用歐拉的方法就能分解了：${\displaystyle 1000009=293\cdot 3413}$。

能用兩種方式把一個整數表示為兩數平方和，或許就能分解這個數，這個想法最早是由梅森提出的。但是直到一百年後，這個想法才得到了廣泛應用。當時歐拉用他的方法分解了 ${\displaystyle 1000009}$，這個方法也由此得名。當時人們還認為 ${\displaystyle 1000009}$ 是質數，但是這個數在主流的素性檢測算法中都不是偽質數。

對於因子相差不是特別小的數，歐拉因式分解法比費馬的方法更高效。如果能比較容易地找出兩種方式把要分解的數表示為兩數平方和，那麼歐拉的方法可能比試除法高效得多。歐拉取得的進展提高了人們分解整數的效率。20 世紀 10 年代，大因數表已經寫到了將近一千萬^{[來源請求]}那麼大了。將數字表示為兩數平方和的方法與在費馬因式分解法（英語：Fermat's factorization method）中查找平方差的方法基本相同。

缺點和限制

歐拉因式分解法最大的缺點是這樣的：要分解的整數，它的質因數分解中，如果有任何一個 4k+3 型的質數是奇數次冪的，那麼歐拉的方法就不能分解了。原因是，這樣的數字不可能是兩數的平方和。4k+1 型的奇合數也經常是兩個 4k+3 型質數的積（例如 3053 = 43 × 71），由上面的結論可以知道，對於這類數，歐拉的方法是用不了的。

這個限制，就讓歐拉因式分解法不太受計算機因子分解算法的歡迎，畢竟對於一個隨機的大數，連能不能用這個方法分解它都很難知道。不過近來，有人嘗試把歐拉的方法發展成計算機算法，用於已知確實可以應用歐拉方法的特定數字。

理論基礎

婆羅摩笈多-斐波那契恆等式指出，一個兩數平方和，和另一個兩數平方和，它們的乘積，是又一個兩數平方和。歐拉的方法就依賴於這個定理，把它反了過來：給定${\displaystyle n=a^{2}+b^{2}=c^{2}+d^{2}}$，那麼${\displaystyle n}$是兩個（可能不一樣的）兩數平方和的積。

首先移項得到

${\displaystyle a^{2}-c^{2}=d^{2}-b^{2}}$

用平方差公式，對兩邊分別因式分解，得到

${\displaystyle (a-c)(a+c)=(d-b)(d+b)}$ (1)

現在令 ${\displaystyle k=\operatorname {gcd} (a-c,d-b)}$，令 ${\displaystyle h=\operatorname {gcd} (a+c,d+b)}$，這樣就有 ${\displaystyle l,m,l',m'}$ 滿足

• ${\displaystyle (a-c)=kl}$,
• ${\displaystyle (d-b)=km}$,

${\displaystyle \operatorname {gcd} (l,m)=1}$

• ${\displaystyle (a+c)=hm'}$,
• ${\displaystyle (d+b)=hl'}$,

${\displaystyle \operatorname {gcd} (l',m')=1}$

把這些代入式 (1)，得到

${\displaystyle klhm'=kmhl'}$

約去 ${\displaystyle k}$ 和 ${\displaystyle h}$，得到

${\displaystyle lm'=l'm}$

我們知道 ${\displaystyle l,m}$ 互素，${\displaystyle l',m'}$ 互素，因此

• ${\displaystyle l=l'}$
• ${\displaystyle m=m'}$

因此

• ${\displaystyle (a-c)=kl}$
• ${\displaystyle (d-b)=km}$
• ${\displaystyle (a+c)=hm}$
• ${\displaystyle (d+b)=hl}$

可以看到 ${\displaystyle m=\operatorname {gcd} (a+c,d-b)}$ 還有 ${\displaystyle l=\operatorname {gcd} (a-c,d+b)}$

現在應用婆羅摩笈多-斐波那契恆等式，我們就得到了

${\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.}$

由於每個因子都是兩數平方和，那麼${\displaystyle (k,h)}$ 和 ${\displaystyle (l,m)}$ 之中必有一個數對中兩個數都是偶數。不失一般性，假設數對${\displaystyle (k,h)}$里兩數都是偶數。於是就可以這樣分解了：

${\displaystyle n=\left(\left({\tfrac {k}{2}}\right)^{2}+\left({\tfrac {h}{2}}\right)^{2}\right)\left(l^{2}+m^{2}\right).\,}$

例子

已知 ${\displaystyle \ 1000009=1000^{2}+3^{2}=972^{2}+235^{2}}$

用上面的方法計算：

a = 1000	(A) a − c = 28	k = gcd[A,C] = 4
b = 3	(B) a + c = 1972	h = gcd[B,D] = 34
c = 972	(C) d − b = 232	l = gcd[A,D] = 14
d = 235	(D) d + b = 238	m = gcd[B,C] = 116

於是

${\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]\,}$

${\displaystyle =\left(2^{2}+17^{2}\right)\cdot \left(7^{2}+58^{2}\right)\,}$

${\displaystyle =(4+289)\cdot (49+3364)\,}$

${\displaystyle =293\cdot 3413\,}$

偽代碼

function Euler_factorize(int n) -> list[int]
   if is_prime(n) then
       print("数字是質數，不能分解")
       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("数字无法表示成平方和")
       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("没有第二种表示成平方和的方法")
       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 ]

參考資料

• Ore, Oystein. Euler's Factorization Method. Number Theory and Its History. Courier Corporation. 1988: 59–64. ISBN 978-0-486-65620-5.
• McKee, James. Turning Euler's Factoring Method into a Factoring Algorithm. Bulletin of the London Mathematical Society. 1996, 4 (28): 351–355. doi:10.1112/blms/28.4.351.