歐拉因式分解法

整数分解方法

歐拉因式分解法是一種整數分解方法,重點是用兩種方式把要分解的數表示為兩數平方和。比如要分解 ,這個數既能寫成 ,又能寫成 ,那麼用歐拉的方法就能分解了:

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

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

缺點和限制

編輯

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

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

理論基礎

編輯

婆羅摩笈多-斐波那契恆等式指出,一個兩數平方和,和另一個兩數平方和,它們的乘積,是又一個兩數平方和。歐拉的方法就依賴於這個定理,把它反了過來:給定 ,那麼 是兩個(可能不一樣的)兩數平方和的積。

首先移項得到

 

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

  (1)

現在令  ,令  ,這樣就有   滿足

  •  ,
  •  ,

 

  •  ,
  •  ,

 

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

 

約去   ,得到

 

我們知道   互素,  互素,因此

  •  
  •  

因此

  •  
  •  
  •  
  •  

可以看到   還有  

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

 

由於每個因子都是兩數平方和,那麼   之中必有一個數對中兩個數都是偶數。不失一般性,假設數對 里兩數都是偶數。於是就可以這樣分解了:

 

例子

編輯

已知  

用上面的方法計算:

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

於是

 
 
 
 

偽代碼

編輯
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 ]

參考資料

編輯