iidaの日記： フェルマー法 6
日記 by
iida
893をフェルマー法で素因数分解しろ、という問題に、30以下の数で割るだけ、という回答があったが、こいつは頂けない。
フェルマー法というなら、
まず、1の自乗を足して平方根を取り整数かどうか見る。
整数でないので、2の自乗を足して平方根を取り整数かどうか見る。
整数でないので、3の自乗を足して平方根を取り整数かどうか見る。…
…こうして14まで行くと、14の自乗つまり196を足すと1,089で、これの平方根をとるとぴったり整数の33。
893+14²=33²だから
893=33²-14²=(33+14)×(33-14)=47×19
とくるのがホントのフェルマー法だろ。
--
iida
フェルマー法って効率悪いっすよね (スコア: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 が存在するかチェックして、素数を判定する方法をフェルマーテストとも言うし、
フェルマー法と間違うのもある意味しょうがないかなと
893の分解なんて (スコア:0)
長ドスの１本もあれば足りるかと。
Re: (スコア:0)
長ドスの１本もあれば足りるかと。
そこはちゃかすな
# なんつって