2

私は宿題のためにこの質問を設定しました：

因数分解への別のアプローチは、1643 年に Fermat によって使用されました。これは、小さい因数よりも大きい因数を見つけるのに適しています。n が奇数であり、n = u × v であると仮定します。n = x^2 − y^2 に従います。ここで、x = (u + v)/2 と y = (v − u)/2 は両方とも整数です。数字（なぜ？）フェルマーの方法は、x^2 − y^2 = n および 0 ≤ y < x となるような y が存在する x の最小値を体系的に検索することで構成されます。

演習 11. x の可能な最小値、つまり検索を開始する値は? ある段階で、検索が x ≥ p および y ≥ q に絞り込まれたとします。r = p^2 − q^2 − n とします。r = 0 の場合、完了です。r < 0 の場合、p または q をどのように変更すればよいでしょうか? また、r = p^2 − q^2 − n を維持するために r を変更するにはどうすればよいでしょうか? r > 0 の場合はどうなるでしょうか。このメソッドがすべての奇数 n で終了することが保証されているのはなぜですか? search pqr が検索を実行するように関数検索を設計します。したがって、与えられた奇数の 2 つの因数を返す関数 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 のような他の数値 ((9,11) ではなく (1,99) を取得) では機能しません。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

このアルゴリズムによって返される 2 つの因数は、素数である場合とそうでない場合があることに注意してください。戻り値がnと 1 の場合、入力nは素数です。このアルゴリズムについては、ブログで説明しています。フェルマーのアルゴリズムは、数値の因数を見つける最悪の方法の 1 つであることに注意してください。nが同様の大きさの 2 つの因数を持つ半素数の場合を除いて、試行分割でさえ通常は高速です。

于 2013-09-11T18:02:10.207 に答える