2

我已经为家庭作业设置了这个问题：

费马在 1643 年使用了另一种因式分解方法。它更适合寻找大因数而不是小因数。假设 n 是一个奇数，并且 n = u × v。由此得出 n = x^2 − y^2 ，其中 x = (u + v)/2 和 y = (v − u)/2 都是整数数字（为什么？）。费马方法包括系统地搜索 x 的最小值，其中存在 x ^2 - y^2 = n 且 0 ≤ y < x 的 y。

练习 11. x 的最小可能值是多少，也就是说，我们应该从这个值开始搜索？假设在某个阶段，搜索范围缩小到 x ≥ p 和 y ≥ q。设 r = p^2 - q^2 - n。如果 r = 0，那么我们就完成了。如果 r < 0，我们应该如何改变 p 或 q？我们如何改变 r 以保持 r = p^2 - q^2 - n？如果 r > 0 怎么办？为什么这种方法保证对所有奇数 n 终止？设计一个函数 search 以便 search pqr 执行搜索。因此设计一个函数 fermat 用于返回给定奇数的两个因子。

这是我到目前为止所拥有的：

type Factors = (Integer, Integer)
search :: Integer -> Integer -> Integer -> Integer -> Factors
search n p q r
   | r == 0    = (p-q,p+q)
   | r < 0     = search n a b c
   | otherwise = search n d b e
      where a = p+1 ; b = isqrt (q*q+2*(p-1)+1) ; c = (a*a-b*b-n) ;
             d = p-1 ; e = (d*d-b*b-n)

isqrt :: Integer -> Integer
isqrt = truncate . sqrt . fromInteger

fermat :: Integer -> Factors
fermat n
  | n == 0    = (0,0)
  | otherwise = search n p q r 
    where p = isqrt(n) ; q = 1 ; r = (p*p-q*q-n)

这适用于某些数字，例如 33（我得到 (3,11) 的预期），但不适用于其他数字，例如 99（我得到 (1,99) 而不是 (9,11)）。我想我需要对 q 的初始值使用不同的东西。一些提示将不胜感激。

我尝试将 q 的初始值更改为isqrt( abs(p*p-n))，但这仍然使 99 为 (3, 33) ，这是不正确的。

4

1 回答 1

1

正如 Daniel Fischer 在他的提示中所暗示的那样，搜索从平方根开始并增加。这是算法，我将把它留给你翻译成 Haskell：

function fermat(n)
    s = floor(sqrt(n))
    u, v, r = 2*s+1, 1, s*s-n
    repeat
        if r > 0 then v, r = v+2, r-v
        else if r < 0 then u, r = u+2, r+u
        else return (u+v-2)/2, (u-v)/2

请注意，此算法返回的两个因子可能是质数，也可能不是质数；如果返回值为n和 1，则输入n是素数。我在我的博客上讨论了这个算法。请注意，费马算法是查找数字因数的最糟糕的方法之一；即使是试除法通常也更快，除了n是具有两个相似大小的因子的半素数的情况。

于 2013-09-11T18:02:10.207 回答