欧拉因式分解法

Template:No footnotes Template:Refimprove 欧拉因式分解法是一种整数分解方法，重点是用两种方式把要分解的数表示为两数平方和。比如要分解 $1000009$，这个数既能写成 $1000^2+3^2$，又能写成 $972^2+235^2$，那么用欧拉的方法就能分解了：$1000009=293\cdot 3413$。

能用两种方式把一个整数表示为两数平方和，或许就能分解这个数，这个想法最早是由梅森提出的。但是直到一百年后，这个想法才得到了广泛应用。当时欧拉用他的方法分解了 $1000009$，这个方法也由此得名。当时人们还认为 $1000009$ 是質數，但是这个数在主流的素性检测算法中都不是伪質數。

对于因子相差不是特别小的数，欧拉因式分解法比费马的方法更高效。如果能比较容易地找出两种方式把要分解的数表示为两数平方和，那么欧拉的方法可能比试除法高效得多。欧拉取得的进展提高了人们分解整数的效率。20 世纪 10 年代，大因数表已经写到了将近一千万Template:Citation needed那么大了。将数字表示为两数平方和的方法与在Template:Tsl中查找平方差的方法基本相同。

缺点和限制

欧拉因式分解法最大的缺点是这样的：要分解的整数，它的质因数分解中，如果有任何一个 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=\gcd (a-c,d-b)$，令 $h=\gcd (a+c,d+b)$，这样就有 $l,m,l^{\prime },m^{\prime }$ 满足

• $(a-c)=kl$,
• $(d-b)=km$,

$\gcd (l,m)=1$

• $(a+c)=h{m}^{\prime }$,
• $(d+b)=h{l}^{\prime }$,

$\gcd (l^{\prime },m^{\prime })=1$

把这些代入式 (1)，得到

$klh{m}^{\prime }=kmh{l}^{\prime }$

约去 $k$ 和 $h$，得到

$l{m}^{\prime }=l^{\prime }m$

我们知道 $l,m$ 互素，$l^{\prime },m^{\prime }$ 互素，因此

• $l=l^{\prime }$
• $m=m^{\prime }$

因此

• $(a-c)=kl$
• $(d-b)=km$
• $(a+c)=hm$
• $(d+b)=hl$

可以看到 $m=\gcd (a+c,d-b)$ 还有 $l=\gcd (a-c,d+b)$

现在应用婆罗摩笈多-斐波那契恒等式，我们就得到了

$(k^2+h^2)(l^2+m^2)=(kl+hm{)}^2+(km-hl{)}^2=((a-c)+(a+c){)}^2+((d-b)-(d+b){)}^2=(2a{)}^2+(2b{)}^2=4n.$

由于每个因子都是两数平方和，那么$(k,h)$ 和 $(l,m)$ 之中必有一个数对中两个数都是偶数。不失一般性，假设数对$(k,h)$里两数都是偶数。于是就可以这样分解了：

$n=({\left(\frac{k}{2}\right)}^2+{\left(\frac{h}{2}\right)}^2)(l^2+m^2).$

例子

已知 $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=[{\left(\frac{4}{2}\right)}^2+{\left(\frac{34}{2}\right)}^2]\cdot [{\left(\frac{14}{2}\right)}^2+{\left(\frac{116}{2}\right)}^2]$

$=(2^2+17^2)\cdot (7^2+58^2)$

$=(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 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 ]

参考资料

• Template:Cite book
• Template:Cite journal