流れる空の中で数学を。

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

【素因数分解】円分多項式法の微改良とテスト計算

前回の記事の円分多項式法のプログラムをさらに改良しました。

 

sky-time-math.hatenablog.jp

 

p\#_n素数階乗としたとき、

a_1=(p\#_n)^{(p\#_n^k)}-1

a_n=(a_{n-1})^{(p\#_n^k)}-1

を計算し、

gcd(a_n,N)

から素因数を計算して、N素因数分解するプログラムに少し改良?しました。

素数階乗に使う素数の個数、指数k、数列の個数nの順に入力すれば計算できます。nlistに素因数分解したい数のリストを入れてください。

テストでは、10桁×20桁の素因数分解を100個行います。成功確率は、100000個の素数k=9,n=1で、約50%です。平均計算時間は4.5秒です。

gistbb369755c4507056bbdd7485fde21693

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

(素数階乗)のk乗ー1にとることで、小さな素数が入り込む確率を減らし、ある程度以上大きな素因数のみを探索できるようにかいりょうしました。また、数列階乗法の知見も少しだけとりいれました。21桁の素因数分解で0.0秒の記録を出しました。

問題は素数何個を事前に準備したらいいかわからない点です。また、必要な素数を拾いきる前に素因数が大きくなり過ぎてしまう恐れがあるので、その可能性も研究しないといけません。プログラムを貼っておきます。素数100個で21桁の素因数分解が0.0秒でできました。

cyclotomic polynomial method ver 2

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

円分多項式

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

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

 

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

【Python】巨大な数の整数平方根のプログラム【改良版】

この前、整数平方根を計算するプログラムを書きました。

 

sky-time-math.hatenablog.jp

 

ところが、前回のバージョンだと600桁を超えた変数を入力したところ、float型が途中で入り込んでいためエラーがでてしまいました。

そこで、今回は、この点を改良したプログラムを公開します。ご自由にお使いください。

Intsqrt ver2

【素因数分解】数列階乗法の改良その1【RSAに挑む】

数列階乗法の改良

前の記事で紹介した数列階乗法では、数列

a_n=a_{n-1}a_{n-2}\cdots a_1+1

x_n=a_n\cdots a_1

としていた。

 

sky-time-math.hatenablog.jp

 

ところが、これでは、x_nを初めて計算するときに新たに含まれる素因数が大きくなり過ぎてしまう恐れがある。実際、素因数分解したい数Nよりおおきな素因数をとりこんでしまった場合、それは新しい素因数としてカウントされない。

そこで、kをなるべく多くの約数を持つ自然数として

a_n=(a_{n-1}a_{n-2}\cdots a_1)^k-1

x_n=a_n\cdots a_1

 という漸化式を用いることにすれば、a_nは、多くの合成数からなることが保証される。

x_n^k-1x_n多項式の積となるが、できればなるべく次数の低い多項式の多くの積からなっていてほしい。または、次数が高くても、十分な数の素因数を持つ確率が高ければいい。このような適切でなるべく大きなkの値の取り方をまだ僕は知らない。

今回はとりあえず、k=210^{10}=(2 \times 3 \times 5 \times 7)^{10}ととってみた。

上にあげた漸化式の形に限らなくても、少ない計算量で、より多くのN以下の素因数の積からなる数列を構成できれば、一気に数列階乗法の可能性は広がる。問題は、そのような都合のいい漸化式が存在するかどうかだ。

プログラム

今回も大規模計算はせず、30分程度以内のテスト計算だけを行った。1つのrsa自然数に対して、一分かからないくらいだった。

当然というか、テスト用の素因数分解以外はうまくいかなかった。最低でも100桁あるので、まだまだチューニングが必要だろう。

 

Sequence factorial method

【Python】数列階乗法のプログラム

前回の記事で紹介した数列階乗法のプログラムを公開します。

 

残念ながら100桁以上の素因数分解は試した範囲では失敗しました。ですが、まだ漸化式を改良したり、初期値の取り方を考慮するなど改善の余地があります。

ご自由に改良して、試行錯誤しながら使ってみてください。

まずは、フィボナッチ数列の漸化式を用いたプログラムから。

gist6c13cec7b7ff12a00b58b90f4b0548be

 

次に、階乗+1の形で生成される。漸化式のバージョンです。

gist478dd0851bb4ae63882d8feacaf8c6d5

 

【素因数分解】数列階乗法【RSAに挑む】

数列階乗法

いきなり、「数列階乗法って何だよ?」って思った方がほとんどだろう。
それも当然で、僕が考えた「数打ちゃ鉄砲当たる形」の新規素因数分解アルゴリズムだからだ。

というわけで、数列階乗法を説明しようと思う。

素因数分解したい数が、N=pq,p,q \gt 1だったとする。

まず、数列a_nを用意する。そして、あるnまでの数列の積のモジュロをとり

x_n=a_n \cdots a_1 mod N

とすると、もし、a_1からa_nの中に素因数pまたはqのいずれか一方が含まれていれば、

gcd(x_n,N)=p

または、

gcd(x_n,N)=q

となる。という非常にシンプルなアイデアである。数列のインデックスを一つずつ減らしながらかけていく様が、階乗に似ているので、数列階乗法となづけた。

どんな数列を使うのか?

数列階乗法の基本アイデアはお判りいただけたかと思う。

最も単純だが計算量が高コストな、数列は、素数列である。素数階乗を順に取っていき、最大公約数を計算すれば必ず小さい方の素因数が引き出せる。しかし、これでは、素数一つ一つについて計算を行うため、計算コストが大きくなってしまう。そこで、多くの素因数を持つ可能性がある(なるべく)合成数からなる数列を用意した方が良いということになる。

漸化式の一例を挙げよう。

a_n=a_{n-1}a_{n-2}\cdots a_1+1

こうしておくと、数列a_nは全て互いに素になる。しかもnが大きくなると、a_nも大きくなるので、1-1/\ln{a_n}の確率で合成数になる。これが非常に多くのN以下の素因数を運よく含んでくれていれば、単純に素因数をかけていくより、合成数をまとめてかけていくことになるので、効率がよくなる。

また、初項a_1の取り方も、1や\sqrt{N}にとるなど、いろいろなパターンが考えらえれる。nを大きく取るか、初項のパターンを増やした方がいいのか、どちらがいいのかはよくわからない。

もう一つの例は、フィボナッチ数列の漸化式である。(もちろんリュカ数列(リュカ数列 - Wikipedia)でもいい。)

F_n=F_{n-1}+F_{n-2}

ここでも、初項F_1,F_2をさまざまな値にとって、数列階乗法を試すことができる。フィボナッチ数列は、mod Nでループすることが知られているので、初期値をいろいろ変えていった方がいいと思われる。

実装が面倒だったのでまだ試していないが、

a_n=a_{n-1}a_{n-2}+1

等も考えられる。

とにもかくにも、 数列階乗法の本質的な強みは、素数の候補をひとつずつ試していく代わりに、合成数としてまとめて試すことで、計算回数を減らす点にある。そのため、a_nがなるべく多くの新しい素因数を一度に含むような合成数になるような数列をみつければいくらでも改良できることになる。なにかいい案はないものだろうか?