欧拉 因式分解法 是一种整数分解 方法,重点是用两种方式把要分解的数表示为两数平方和。比如要分解
1000009
{\displaystyle 1000009}
,这个数既能写成
1000
2
+
3
2
{\displaystyle 1000^{2}+3^{2}}
,又能写成
972
2
+
235
2
{\displaystyle 972^{2}+235^{2}}
,那么用欧拉的方法就能分解了:
1000009
=
293
⋅
3413
{\displaystyle 1000009=293\cdot 3413}
。
能用两种方式把一个整数表示为两数平方和,或许就能分解这个数,这个想法最早是由梅森 提出的。但是直到一百年后,这个想法才得到了广泛应用。当时欧拉用他的方法分解了
1000009
{\displaystyle 1000009}
,这个方法也由此得名。当时人们还认为
1000009
{\displaystyle 1000009}
是質數,但是这个数在主流的素性检测算法中都不是伪質數 。
对于因子相差不是特别小的数,欧拉因式分解法比费马的方法更高效。如果能比较容易地找出两种方式把要分解的数表示为两数平方和,那么欧拉的方法可能比试除法 高效得多。欧拉取得的进展提高了人们分解整数的效率。20 世纪 10 年代,大因数表已经写到了将近一千万[來源請求] 那么大了。将数字表示为两数平方和的方法与在费马因式分解法 中查找平方差的方法基本相同。
缺点和限制
欧拉因式分解法最大的缺点是这样的:要分解的整数,它的质因数分解中,如果有任何一个 4k+3 型的質數是奇数次幂的,那么欧拉的方法就不能分解了。原因是,这样的数字不可能是两数的平方和。4k+1 型的奇合数也经常是两个 4k+3 型質數的积(例如 3053 = 43 × 71),由上面的结论可以知道,对于这类数,欧拉的方法是用不了的。
这个限制,就让欧拉因式分解法不太受计算机因子分解算法的欢迎,毕竟对于一个随机的大数,连能不能用这个方法分解它都很难知道。不过近来,有人尝试把欧拉的方法发展成计算机算法,用于已知确实可以应用欧拉方法的特定数字。
理论基础
婆罗摩笈多-斐波那契恒等式 指出,一个两数平方和,和另一个两数平方和,它们的乘积,是又一个两数平方和。欧拉的方法就依赖于这个定理,把它反了过来:给定
n
=
a
2
+
b
2
=
c
2
+
d
2
{\displaystyle n=a^{2}+b^{2}=c^{2}+d^{2}}
,那么
n
{\displaystyle n}
是两个(可能不一样的)两数平方和的积。
首先移项得到
a
2
−
c
2
=
d
2
−
b
2
{\displaystyle a^{2}-c^{2}=d^{2}-b^{2}}
用平方差公式 ,对两边分别因式分解 ,得到
(
a
−
c
)
(
a
+
c
)
=
(
d
−
b
)
(
d
+
b
)
{\displaystyle (a-c)(a+c)=(d-b)(d+b)}
(1)
现在令
k
=
gcd
(
a
−
c
,
d
−
b
)
{\displaystyle k=\operatorname {gcd} (a-c,d-b)}
,令
h
=
gcd
(
a
+
c
,
d
+
b
)
{\displaystyle h=\operatorname {gcd} (a+c,d+b)}
,这样就有
l
,
m
,
l
′
,
m
′
{\displaystyle l,m,l',m'}
满足
(
a
−
c
)
=
k
l
{\displaystyle (a-c)=kl}
,
(
d
−
b
)
=
k
m
{\displaystyle (d-b)=km}
,
gcd
(
l
,
m
)
=
1
{\displaystyle \operatorname {gcd} (l,m)=1}
(
a
+
c
)
=
h
m
′
{\displaystyle (a+c)=hm'}
,
(
d
+
b
)
=
h
l
′
{\displaystyle (d+b)=hl'}
,
gcd
(
l
′
,
m
′
)
=
1
{\displaystyle \operatorname {gcd} (l',m')=1}
把这些代入式 (1),得到
k
l
h
m
′
=
k
m
h
l
′
{\displaystyle klhm'=kmhl'}
约去
k
{\displaystyle k}
和
h
{\displaystyle h}
,得到
l
m
′
=
l
′
m
{\displaystyle lm'=l'm}
我们知道
l
,
m
{\displaystyle l,m}
互素,
l
′
,
m
′
{\displaystyle l',m'}
互素,因此
l
=
l
′
{\displaystyle l=l'}
m
=
m
′
{\displaystyle m=m'}
因此
(
a
−
c
)
=
k
l
{\displaystyle (a-c)=kl}
(
d
−
b
)
=
k
m
{\displaystyle (d-b)=km}
(
a
+
c
)
=
h
m
{\displaystyle (a+c)=hm}
(
d
+
b
)
=
h
l
{\displaystyle (d+b)=hl}
可以看到
m
=
gcd
(
a
+
c
,
d
−
b
)
{\displaystyle m=\operatorname {gcd} (a+c,d-b)}
还有
l
=
gcd
(
a
−
c
,
d
+
b
)
{\displaystyle l=\operatorname {gcd} (a-c,d+b)}
现在应用婆罗摩笈多-斐波那契恒等式 ,我们就得到了
(
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.}
由于每个因子都是两数平方和,那么
(
k
,
h
)
{\displaystyle (k,h)}
和
(
l
,
m
)
{\displaystyle (l,m)}
之中必有一个数对中两个数都是偶数。不失一般性,假设数对
(
k
,
h
)
{\displaystyle (k,h)}
里两数都是偶数。于是就可以这样分解了:
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).\,}
例子
已知
1000009
=
1000
2
+
3
2
=
972
2
+
235
2
{\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
于是
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\,}
伪代码
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 ]
参考资料