【素因数分解】円分多項式法【RSAに挑む】
Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴
円分多項式法
「円分多項式法って何よ？」っていわれそうなので、先に言っておきます。僕が考えたおそらく最強の素因数分解アルゴリズムです。改良の余地がまだ残っています。今後、弱点が見つかる可能性もありますが……
基本的には、素数階乗法の改良となっています。
では、説明です。
円分多項式
を考えます。ここで、をm個の素数の素数階乗(素数階乗 - Wikipedia)にとると、この多項式は、
の多項式として、
個の多項式に因数分解されます。
と適当な値を割り振れば、xは非常に多くの素因数からなる合成数になります。この素因数の分布の
依存性がわからないのが悩みの種ですが、とにもかくにもこれを使って自然数
を素因数分解してみます。
が
または
の一方のみを含んでいれば、
または
となります。これだけです。
傾向として、kを大きな素数階乗に取るとが
の倍数になる確率があがってしまいます。
一方で、が小さすぎると、
いずれも含まない確率が上がってしまいます。
素数階乗で素数を何個とるか見極めることがポイントになってきます。
プログラム
素数階乗で何個素数をとるかをインプットで聞いてきますので、自然数を入力してください。nlistで素因数分解したい数のリストを書き足していただければ、自動で素因数分解してくれます。答えは、Ansで検索できます。
素因数の個数が大きすぎると、計算途中でpqと出力されるので、数を減らしてください。何も表示されず計算が終わってしまった場合は、素数の個数を調整してください。また、円分多項式法では拾いきれない特殊な素数が存在する可能性があるのでいくらやっても無駄な可能性もあります。
テストの２１桁の合成数の場合とかとると0.0009秒くらいで分解できました。もっと小さくてもうまくいくと思いますが、面倒なので試してません。
もし、このプログラムを使ってRSA100以降のどれかが分解出来たらご報告よろしくお願いいたします。
