欧拉因式分解法

整数分解方法

欧拉因式分解法是一种整数分解方法,重点是用两种方式把要分解的数表示为两数平方和。比如要分解 ,这个数既能写成 ,又能写成 ,那么用欧拉的方法就能分解了:

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

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

缺点和限制

编辑

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

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

理论基础

编辑

婆罗摩笈多-斐波那契恒等式指出,一个两数平方和,和另一个两数平方和,它们的乘积,是又一个两数平方和。欧拉的方法就依赖于这个定理,把它反了过来:给定 ,那么 是两个(可能不一样的)两数平方和的积。

首先移项得到

 

平方差公式,对两边分别因式分解,得到

  (1)

现在令  ,令  ,这样就有   满足

  •  ,
  •  ,

 

  •  ,
  •  ,

 

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

 

约去   ,得到

 

我们知道   互素,  互素,因此

  •  
  •  

因此

  •  
  •  
  •  
  •  

可以看到   还有  

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

 

由于每个因子都是两数平方和,那么   之中必有一个数对中两个数都是偶数。不失一般性,假设数对 里两数都是偶数。于是就可以这样分解了:

 

例子

编辑

已知  

用上面的方法计算:

a = 1000 (A) ac = 28 k = gcd[A,C] = 4
b = 3 (B) a + c = 1972 h = gcd[B,D] = 34
c = 972 (C) db = 232 l = gcd[A,D] = 14
d = 235 (D) d + b = 238 m = gcd[B,C] = 116

于是

 
 
 
 

伪代码

编辑
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 ]

参考资料

编辑