流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

【素因数分解】円分多項式法【RSAに挑む】

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます!

円分多項式

「円分多項式法って何よ?」っていわれそうなので、先に言っておきます。僕が考えたおそらく最強の素因数分解アルゴリズムです。改良の余地がまだ残っています。今後、弱点が見つかる可能性もありますが……

基本的には、素数階乗法の改良となっています。

 

sky-time-math.hatenablog.jp

 

では、説明です。

円分多項式

x=n^k-1

を考えます。ここで、kをm個の素数素数階乗(素数階乗 - Wikipedia)にとると、この多項式は、n多項式として、2^m個の多項式因数分解されます。n=2,3,4,\cdotsと適当な値を割り振れば、xは非常に多くの素因数からなる合成数になります。この素因数の分布のk,n依存性がわからないのが悩みの種ですが、とにもかくにもこれを使って自然数N=pq,p, q \gt 2素因数分解してみます。xpまたはqの一方のみを含んでいれば、

\gcd(x,N)=p

または

\gcd(x,N)=q

となります。これだけです。

傾向として、kを大きな素数階乗に取るとxpqの倍数になる確率があがってしまいます。

一方で、kが小さすぎると、p,qいずれも含まない確率が上がってしまいます。

素数階乗で素数を何個とるか見極めることがポイントになってきます。

プログラム

素数階乗で何個素数をとるかをインプットで聞いてきますので、自然数を入力してください。nlistで素因数分解したい数のリストを書き足していただければ、自動で素因数分解してくれます。答えは、Ansで検索できます。

素因数の個数が大きすぎると、計算途中でpqと出力されるので、数を減らしてください。何も表示されず計算が終わってしまった場合は、素数の個数を調整してください。また、円分多項式法では拾いきれない特殊な素数が存在する可能性があるのでいくらやっても無駄な可能性もあります。

テストの21桁の合成数の場合k=300とかとると0.0009秒くらいで分解できました。もっと小さくてもうまくいくと思いますが、面倒なので試してません。

もし、このプログラムを使ってRSA100以降のどれかが分解出来たらご報告よろしくお願いいたします。

cyclotomic polynomial method