掲示板お問い合わせランダムジャンプ

トップスペース

2014年08月29日
【コミPo】「ポラード・ロー素因数分解法」の基本的なことを解説
 最近、素因数分解に興味を待ち、JavaScriptによる素因数分解のプログラムを作っていたりします。
 素因数分解は桁数が増えるごとに計算量が増え、解くのが難しくなることから暗号にも使われていて云々、というのは有名だと思います。

 で、高速に解くためには様々なアルゴリズムがあるわけですが、今回は「ポラード・ロー素因数分解法」というのを試しています。このアルゴリズムについてはWikipediaで説明されています。
 ポラード・ロー素因数分解法 - Wikipedia

 さて、上のwikipediaは読んでもよく分からなかったりします。これに限らずWikipediaは難しくてよく分からないものが多いです。
 そこで解説漫画のようなものを作ってみました。

Pollard's rho algorithm

 たぶん根本的な原理はこれで間違いないはず。

 これ以上のことは以下のサイトがとても参考になります。
 ρ法 @ 素因数分解 @ IDM
[ 投稿者:うえぽん at 19:51 | 自作4コマなど | コメント(5) ]

この記事へのコメント
無題
つまり如何に都合の良い乱数を生成するかに問題が帰着するんでしょうか
それはもう乱数では無いのかな
投稿者: murasaki at 2014-08-31 01:30:15
乱数
数学の難しいことはよく分かりませんが、色々試してみた感じでは、アルゴリズム説明のために紹介されていたこの乱数が一番速かったです。

この「二乗して余りを求める」というのが重かったりします。
なぜなら、二乗するとオーバーフローしてしまうので、乗算を足し算に分解して計算しなければいけません。
三乗、四乗となるとさらに重たくなっていくので、最終的にはシンプルな「二乗して余りを求める」に落ち着くのかもしれません。
投稿者: うえぽん at 2014-08-31 06:53:54
無題
このアルゴリズムで因数Pの倍数を求めたあと、またそれを素因数分解して因数Pを求めるのですか。
投稿者: パリ at 2016-08-21 20:19:47
合成数ならさらに素因数分解します
>このアルゴリズムで因数Pの倍数を求めたあと、またそれを素因数分解して因数Pを求めるのですか。

素数であるか判定し、素数なら終了、素数でない(合成数)ならさらに素因数分解すれば良いかと思います。
素数判定は素因数分解より速くできます。
詳しくは「ミラー・ラビン素数判定法」で検索してみてください。
ただし「ミラー・ラビン素数判定法」は確率的アルゴリズムです。検証された範囲でしか決定的アルゴリズムとしては使えないので注意してください。
投稿者: うえぽん at 2016-08-21 20:51:39
無題
ありがとうございます。
ポラード・ロー法で得られた因数をまたひたすら割っていったら試し割り法と大して実行時間が変わらなくなってしまうのではないかと思ったのですが、素数の因数が得られた場合ミラーラビン素数判定法などの素数判定アルゴリズムを使えばずっと高速に素因数分解できるのですね。
投稿者: パリ at 2016-08-22 04:13:41

この記事の固定URL
http://shinshu.fm/MHz/14.30/archives/0000448516.html

記事へのコメント
 
簡単演算認証: 6 x 8 + 5 =
計算の答えを半角英数字で入力して下さい。
名前: [必須]
URL/Email:
タイトル:
コメント:
※記事・コメントなどの削除要請はこちら