アカウント名:
パスワード:
この質問 [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=246892=(224+222)(224-222)=2×446
1²から試していくと大きさの近い約数が2つが取れる利点がありそう。あと4で割り切れない偶数はフェルマー法で因数分解できないのかな?
4で割り切れない偶数は、因数分解できない。なぜならa+bとa-bは、その両方が偶数か、両方が奇数であって、整数の範囲では片方偶数片方奇数になることはないから。
元の質問を読むと、いわゆる「フェルマーの小定理を使って、素数を判定する」ことを回答者はフェルマ-法と思って回答したみたいですね。
a^{p-1} !≡ 1 (mod p) ((a, p) = 1) となる a が存在するかチェックして、素数を判定する方法をフェルマーテストとも言うし、フェルマー法と間違うのもある意味しょうがないかなと
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
アレゲは一日にしてならず -- アレゲ研究家
フェルマー法って効率悪いっすよね (スコア:1)
この質問 [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) で、前回の計算結果から軽い足し算で計算できるし。
平方数判定も、候補は単調増加なので、いちいち平方根を取らなくても、あらかじめ候補を出しておいて比較すればいいので、
ループ中は割算も掛算も要らない。
まあ、今時あまり意味ないですが。
Re:フェルマー法って効率悪いっすよね (スコア: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で割り切れない偶数はフェルマー法で因数分解できないのかな?
Re: (スコア:0)
4で割り切れない偶数は、因数分解できない。
なぜならa+bとa-bは、その両方が偶数か、両方が奇数であって、整数の範囲では片方偶数片方奇数になることはないから。
Re: (スコア:0)
元の質問を読むと、いわゆる「フェルマーの小定理を使って、素数を判定する」ことを回答者はフェルマ-法と思って回答したみたいですね。
a^{p-1} !≡ 1 (mod p) ((a, p) = 1) となる a が存在するかチェックして、素数を判定する方法をフェルマーテストとも言うし、
フェルマー法と間違うのもある意味しょうがないかなと