楕円曲線上での点移動による素因数探索

マガジンご購読の皆様、こんにちは。いかがお過ごしでしょうか。

このところ、小学生がやるような素因数分解を大きな桁数でも高速にやれないかと思って、遊んでおります。いちおう、昨日までに、Pollard's rho アルゴリズムと Pollards's p-1 法のどちらでも選んで素因数分解を行えるようなプログラムが完成しました。FireMonkey版ですので、その気になれば、iOS, Android, Mac OS などに簡単に移植できますが、当面、64 bit Windowsで動かすことを前提に作っています。

最初のころは、Webサイトでは対応していないことの多い17桁とか、20桁とかの整数の素因数を乱数発生させる Pollard's rho アルゴリズムで簡単に発見できるだけで喜んでいたのですが、これは、まったくの素人のぬかよろこびと判明しました。なぜならば、ここから先、桁数が増えると急速に手が出せなくなるからです。

それでも、Pollard's rho アルゴリズム、78桁のフェルマー数の素因数を Windows 11 のダイナブックで１４分で見つけてくれました。たまたま運がいいような数字だったということもあるでしょう。他の数字で、７０～１００桁のものが同じようにできればよいのですが、どうも難しいようです。

ということで、他の方法に切り替え、p-1法を取り入れ、２０桁くらいだと、Pollard's rho アルゴリズムの１０倍以上高速化できることがわかり、そこは満足だったのですが、やはり、大きな桁数の数字には難があります。私は単純な階乗計算だけしか使っておらず、あまり最適化していないので、そこは問題がまだあるかもしれませんが、印象としては、少々の改良では難しいかなというところです。

そこで、いま検討しているのは、楕円曲線法です。楕円曲線上で、整数の演算を行いつつ、素因数の探索を行うというものです。オランダの数学者 H. W. Lenstra, Jr が見出した手法です。

p-1 法との対比で言えば、同じ階乗計算を導入するにしても、この楕円曲線上の整数座標の点P(x, y) に対しての計算に置き代えると、非常に速くなるという点が注目されます。

ここでいう「楕円曲線　y^2=x^3 + ax + b mod N   上の演算」とは、この曲線上に２点あるとき、その２点を通る直線の傾き（これも mod N　で扱う）を求め、その傾きから、第３点のX座標、Y座標を計算する（これも mod N　で）といった演算です。

階乗計算も最初は2! ですので、これは同じ点を２回足す操作になります。このときは傾きは微分で与えられる式（(3x1^2 +a)/2y1 mod N）で求めます。その次は、3! になりますが、3×2! ですので、つまり、さっき求めた新しい点を３回足す操作になります。いっぺんに３つは足せませんので、順番にやります。最初は微分で求まる傾き、その次は、さらに新しく求まった点に対する傾きを使います。

こういった操作で大きな整数を短時間でサーベイしようというわけです。この計算のなかで、傾きの分母にあたる部分が mod N としたときに1以外の値をとるとき、そこで計算を止めます。その値と、Nの最大公約数が答えになります。

ご意見・ご感想を歓迎します

本記事についてのご意見、ご感想は、twitter のダイレクトメールで承っております。また、マガジンご購読の皆様には、種々のコミュニケーションの機会をご案内いたします。その折には、なんでもおっしゃってください。どんなご質問にもお答えしております。

初めての皆様へ

皆様には、桜井健次のエッセイのマガジン「群盲評象」をお薦めしております。どんな記事が出ているか、代表的なものを「群盲評象ショーケース（無料）」に収めております。もし、こういうものを毎日お読みになりたいという方は、1年分ずっと読める「群盲評象2022」を、また、お試しで1か月だけ読んでみようかという方は「月刊群盲評象」をどうぞ。毎日、マガジンご購読の皆様にむけて、ぜひシェアしたいと思うことを語っております。

群盲評象ショーケース（無料）｜桜井健次｜note