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

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

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

数列階乗法

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

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

素因数分解したい数が、 $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がなるべく多くの新しい素因数を一度に含むような合成数になるような数列をみつければいくらでも改良できることになる。なにかいい案はないものだろうか？