主題
Search

尤拉分解法

一種分解演算法，透過將 N 表示為兩種不同的二次形式來工作。然後

N=a^2+b^2=c^2+d^2,
(1)

所以

a^2-c^2=d^2-b^2
(2)
(a-c)(a+c)=(d-b)(d+b).
(3)

令 k 為 最大公約數 of a-c 和 d-b 所以

a-c=kl
(4)
d-b=km
(5)
(l,m)=1,
(6)

（其中 (l,m) 表示 最大公約數 of l 和 m），並且

l(a+c)=m(d+b).
(7)

但是由於 (l,m)=1, m|a+c 並且

a+c=mn,
(8)

這得出

b+d=ln,
(9)

所以我們有

[(1/2k)^2+(1/2n)^2](l^2+m^2)=1/4(k^2+n^2)(l^2+m^2)
(10)
=1/4[(km)^2+(kl)^2+(nm)^2+(nl)^2]
(11)
=1/4[(d-b)^2+(a-c)^2+(a+c)^2+(d+b)^2]
(12)
=1/4(2a^2+2b^2+2c^2+2d^2)
(13)
=1/4(2N+2N)
(14)
=N.
(15)

另請參閱

質因數分解演算法

使用 探索

請引用為

韋斯坦, 埃裡克·W. “尤拉分解法。” 來自——Wolfram 網路資源。 https://mathworld.tw/EulersFactorizationMethod.html

主題分類