【素因数分解】数列階乗法の改良その1【RSAに挑む】
Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴
数列階乗法の改良
前の記事で紹介した数列階乗法では、数列
としていた。
ところが、これでは、を初めて計算するときに新たに含まれる素因数が大きくなり過ぎてしまう恐れがある。実際、素因数分解したい数Nよりおおきな素因数をとりこんでしまった場合、それは新しい素因数としてカウントされない。
そこで、kをなるべく多くの約数を持つ自然数として
という漸化式を用いることにすれば、は、多くの合成数からなることが保証される。
はの多項式の積となるが、できればなるべく次数の低い多項式の多くの積からなっていてほしい。または、次数が高くても、十分な数の素因数を持つ確率が高ければいい。このような適切でなるべく大きなkの値の取り方をまだ僕は知らない。
今回はとりあえず、ととってみた。
上にあげた漸化式の形に限らなくても、少ない計算量で、より多くのN以下の素因数の積からなる数列を構成できれば、一気に数列階乗法の可能性は広がる。問題は、そのような都合のいい漸化式が存在するかどうかだ。
プログラム
今回も大規模計算はせず、30分程度以内のテスト計算だけを行った。1つのrsaの自然数に対して、一分かからないくらいだった。
当然というか、テスト用の素因数分解以外はうまくいかなかった。最低でも100桁あるので、まだまだチューニングが必要だろう。