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

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

  • この質問 [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を√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は、その両方が偶数か、両方が奇数であって、整数の範囲では片方偶数片方奇数になることはないから。

身近な人の偉大さは半減する -- あるアレゲ人

処理中...