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