![見出し画像](https://assets.st-note.com/production/uploads/images/81884294/rectangle_large_type_2_1e439ad01c5d64ca0272c43729fd5b42.jpeg?width=1200)
楕円曲線上での点移動による素因数探索
マガジンご購読の皆様、こんにちは。いかがお過ごしでしょうか。
このところ、小学生がやるような素因数分解を大きな桁数でも高速にやれないかと思って、遊んでおります。いちおう、昨日までに、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 のダイナブックで14分で見つけてくれました。たまたま運がいいような数字だったということもあるでしょう。他の数字で、70~100桁のものが同じようにできればよいのですが、どうも難しいようです。
ということで、他の方法に切り替え、p-1法を取り入れ、20桁くらいだと、Pollard's rho アルゴリズムの10倍以上高速化できることがわかり、そこは満足だったのですが、やはり、大きな桁数の数字には難があります。私は単純な階乗計算だけしか使っておらず、あまり最適化していないので、そこは問題がまだあるかもしれませんが、印象としては、少々の改良では難しいかなというところです。
そこで、いま検討しているのは、楕円曲線法です。楕円曲線上で、整数の演算を行いつつ、素因数の探索を行うというものです。オランダの数学者 H. W. Lenstra, Jr が見出した手法です。
![](https://assets.st-note.com/img/1652794012589-9TC7mclrmf.png?width=1200)
p-1 法との対比で言えば、同じ階乗計算を導入するにしても、この楕円曲線上の整数座標の点P(x, y) に対しての計算に置き代えると、非常に速くなるという点が注目されます。
ここでいう「楕円曲線 y^2=x^3 + ax + b mod N 上の演算」とは、この曲線上に2点あるとき、その2点を通る直線の傾き(これも mod N で扱う)を求め、その傾きから、第3点のX座標、Y座標を計算する(これも mod N で)といった演算です。
階乗計算も最初は2! ですので、これは同じ点を2回足す操作になります。このときは傾きは微分で与えられる式((3x1^2 +a)/2y1 mod N)で求めます。その次は、3! になりますが、3×2! ですので、つまり、さっき求めた新しい点を3回足す操作になります。いっぺんに3つは足せませんので、順番にやります。最初は微分で求まる傾き、その次は、さらに新しく求まった点に対する傾きを使います。
こういった操作で大きな整数を短時間でサーベイしようというわけです。この計算のなかで、傾きの分母にあたる部分が mod N としたときに1以外の値をとるとき、そこで計算を止めます。その値と、Nの最大公約数が答えになります。
ご意見・ご感想を歓迎します
本記事についてのご意見、ご感想は、twitter のダイレクトメールで承っております。また、マガジンご購読の皆様には、種々のコミュニケーションの機会をご案内いたします。その折には、なんでもおっしゃってください。どんなご質問にもお答えしております。
初めての皆様へ
皆様には、桜井健次のエッセイのマガジン「群盲評象」をお薦めしております。どんな記事が出ているか、代表的なものを「群盲評象ショーケース(無料)」に収めております。もし、こういうものを毎日お読みになりたいという方は、1年分ずっと読める「群盲評象2022」を、また、お試しで1か月だけ読んでみようかという方は「月刊群盲評象」をどうぞ。毎日、マガジンご購読の皆様にむけて、ぜひシェアしたいと思うことを語っております。
ここから先は
![](https://assets.st-note.com/production/uploads/images/112709579/profile_81b000f2a46d92b347baf80ad578c149.png?fit=bounds&format=jpeg&quality=85&width=330)
月刊「群盲評象」(試読ご希望の方向け)
現代は科学が進歩した時代だとよく言われます。知識を獲得するほど新たな謎が深まり、広大な未知の世界が広がります。知は無知とセットになっていま…
いつもお読みくださり、ありがとうございます。もし私の記事にご興味をお持ちいただけるようでしたら、ぜひマガジンをご検討いただけないでしょうか。毎日書いております。見本は「群盲評象ショーケース(無料)」をご覧になってください。