主题
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.net.cn/EulersFactorizationMethod.html

主题分类