查看“︁欧拉因式分解法”︁的源代码

{{No footnotes|time=2024-03-14T14:15:28+00:00}}
{{Refimprove|time=2024-03-14T14:15:28+00:00}}
'''[[欧拉]]因式分解法'''是一种[[整数分解]]方法，重点是用两种方式把要分解的数表示为两数平方和。比如要分解 <math>1000009</math>，这个数既能写成 <math>1000^2 + 3^2</math>，又能写成 <math>972^2 + 235^2</math>，那么用欧拉的方法就能分解了：<math>1000009 = 293 \cdot 3413</math>。

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

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

== 缺点和限制 ==

欧拉因式分解法最大的缺点是这样的：要分解的整数，它的质因数分解中，如果有任何一个 4k+3 型的質數是奇数次幂的，那么欧拉的方法就不能分解了。原因是，这样的数字不可能是两数的平方和。4k+1 型的奇合数也经常是两个 4k+3 型質數的积（例如 3053 = 43 × 71），由上面的结论可以知道，对于这类数，欧拉的方法是用不了的。

这个限制，就让欧拉因式分解法不太受计算机因子分解算法的欢迎，毕竟对于一个随机的大数，连能不能用这个方法分解它都很难知道。不过近来，有人尝试把欧拉的方法发展成计算机算法，用于已知确实可以应用欧拉方法的特定数字。

== 理论基础 ==

[[婆罗摩笈多-斐波那契恒等式]]指出，一个两数平方和，和另一个两数平方和，它们的乘积，是又一个两数平方和。欧拉的方法就依赖于这个定理，把它反了过来：给定<math>n=a^2+b^2=c^2+d^2</math>，那么<math>n</math>是两个（可能不一样的）两数平方和的积。

首先移项得到

:<math>a^2 - c^2 = d^2 - b^2</math>

用[[平方差公式]]，对两边分别[[因式分解]]，得到

:<math>(a-c)(a+c) = (d-b)(d+b)</math> (1)

现在令 <math>k = \operatorname{gcd}(a-c, d-b)</math>，令 <math>h = \operatorname{gcd}(a+c,d+b)</math>，这样就有 <math>l,m,l',m'</math> 满足

* <math>(a-c) = kl</math>, 
* <math>(d-b) = km</math>,
<math>\operatorname{gcd}(l,m) = 1</math>
* <math>(a+c) = hm'</math>,
* <math>(d+b) = hl'</math>,
<math>\operatorname{gcd}(l',m') = 1</math>

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

:<math>klhm' = kmhl'</math>

约去 <math>k</math> 和 <math>h</math>，得到

:<math>lm' = l'm</math>

我们知道 <math>l, m</math> 互素，<math>l', m'</math> 互素，因此

* <math>l = l'</math>
* <math>m = m'</math>

因此

* <math>(a-c) = kl</math>
* <math>(d-b) = km</math>
* <math>(a+c) = hm</math>
* <math>(d+b) = hl</math>

可以看到 <math>m = \operatorname{gcd}(a+c,d-b)</math> 还有 <math>l = \operatorname{gcd}(a-c,d+b)</math>

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

:<math>\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.</math>

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

:<math>n = \left(\left(\tfrac{k}{2}\right)^2 + \left(\tfrac{h}{2}\right)^2\right)\left(l^2 + m^2\right). \,</math>

== 例子 ==

已知 <math>\ 1000009 = 1000^2 + 3^2 = 972^2 + 235^2</math>

用上面的方法计算：

{| class="wikitable"
|-
|''a'' = 1000
|(A) ''a'' &minus; ''c'' = 28
| ''k'' = gcd[A,C] = 4
|-
|''b'' = 3
|(B) ''a'' + ''c'' = 1972
| ''h'' = gcd[B,D] = 34
|-
|''c'' = 972
|(C) ''d'' &minus; ''b'' = 232
| ''l'' = gcd[A,D] = 14
|-
|''d'' = 235
|(D) ''d'' + ''b'' = 238
| ''m'' = gcd[B,C] = 116
|}

于是

:<math> 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] \, </math>
::<math>= \left(2^2 + 17^2\right) \cdot \left(7^2 + 58^2\right) \, </math>
::<math>= (4 + 289) \cdot (49 + 3364) \, </math>
::<math>= 293 \cdot 3413 \, </math>

== 伪代码 ==
 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 ]

== 参考资料 ==
* {{Cite book|chapter=Euler's Factorization Method|last=Ore|first=Oystein|title=Number Theory and Its History|pages=[https://archive.org/details/numbertheoryitsh0000orey/page/59 59–64]|isbn=978-0-486-65620-5|year=1988|publisher=Courier Corporation |chapter-url=https://archive.org/details/numbertheoryitsh0000orey/page/59}}
* {{Cite journal|last=McKee|first= James|title=Turning Euler's Factoring Method into a Factoring Algorithm|journal=Bulletin of the London Mathematical Society|year= 1996| issue =28 |volume= 4|pages= 351–355|doi=10.1112/blms/28.4.351}}

{{数论算法}}

[[Category:整数分解算法]]