パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

フェルマー法」記事へのコメント

  • この質問 [yahoo.co.jp]ですかね?
    誤った回答に対してベストアンサーが付くのは、実にYahoo知恵袋。

    それはさておき、フェルマー法は
    N = a2 - b2 = (a+b)(a-b)
    という形で素因数を探す、という点ではaとbとのどちらをループ回しても同じですが、
    アルゴリズム的には上からやるものだと思います。
    302 - 893 = 7 : 平方数でない
    312 - 893 = 68 : 平方数でない
    322 - 893 = 131 : 平方数でない
    332 - 893 = 196 : 平方数 142
      → 893 = 332 - 142 = (33+14)(33-14) = 47 × 19
    って感じ。

    その試行回数は、Nから偶数は除外しておくと、
    3の倍数つまり a+b=N/3、a-b=3 になるのが最悪ケースで、a=N/6+3/2、b=N/6-3/2
    ですから、aもbも、おおよそ N/6まで試行する必要があります。

    bを変えていく場合は1から始めますけど、
    aを変えていく場合は√Nから始めるので、こちらの方がちょっと探索範囲が狭い。

    たとえば、879の素因数分解なら、

    bを1から増やす方法
    879+12 = 880 : 平方数でない
    879+22 = 883 : 平方数でない

    879+1452 = 21904: 平方数 1482
    →879 = 1482 - 1452 = (148+145) (148-145) = 297×3
    以上試行回数145回

    aを√Nから増やす方法
    302-879 = 21 : 平方数でない
    312-879 = 82 : 平方数でない

    1482-879 = 21205: 平方数 1452
    →879 = 1482 - 1452 = (148+145) (148-145) = 297×3
    以上、試行回数 119回
    といった感じ。

    どっちにせよ、試し割り法(1~√Nの素数で割ってみる)だと、
    試行数は2~30の素数で10通り
    2と3以降の奇数での試行でも15通りなので、
    それと比べるとフェルマー法って試行回数が多いです。

    その代わり、割算を使わないのがメリットかな。
    平方の計算は(n+1)2 = n2 + (2n+1) で、前回の計算結果から軽い足し算で計算できるし。
    平方数判定も、候補は単調増加なので、いちいち平方根を取らなくても、あらかじめ候補を出しておいて比較すればいいので、
    ループ中は割算も掛算も要らない。
    まあ、今時あまり意味ないですが。

    • >aを√Nから増やす方法
      フェルマー法初めて知って1²から試していたが減らしていくなら√NからではなくN/2以上の最小の整数じゃないか。
      N=892の時、√892=29.86...、892/2=246
      892=(224+222)(224-222)=2×446

      1²から試していくと大きさの近い約数が2つが取れる利点がありそう。
      あと4で割り切れない偶数はフェルマー法で因数分解できないのかな?

      親コメント
      • by Anonymous Coward

        4で割り切れない偶数は、因数分解できない。
        なぜならa+bとa-bは、その両方が偶数か、両方が奇数であって、整数の範囲では片方偶数片方奇数になることはないから。

    • by Anonymous Coward

      元の質問を読むと、いわゆる「フェルマーの小定理を使って、素数を判定する」ことを回答者はフェルマ-法と思って回答したみたいですね。

      a^{p-1} !≡ 1 (mod p) ((a, p) = 1) となる a が存在するかチェックして、素数を判定する方法をフェルマーテストとも言うし、
      フェルマー法と間違うのもある意味しょうがないかなと

アレゲは一日にしてならず -- アレゲ研究家

処理中...