高速な素因数分解アルゴリズム(Lenstra の楕円曲線法)を実装する

はじめに

春休みに入ってからというもの,腰痛が悪化する一方です.

TL; DR

Lenstra の楕円曲線法とは?

素因数分解アルゴリズムの一種で,現時点で見つかっているアルゴリズムの中では3番目に高速だと言われています.Hendrik Lenstra によって考案されたらしいです.

この記事では,Lenstra の楕円曲線法(以下 ECM と略称します)について,アルゴリズムや実行結果,原理などを簡単にまとめていこうと思います.

前提

くどくならない程度に前提となる数学的基礎を紹介しておきます.興味のない人は読み飛ばした方がいいかもしれません.

方程式  y^2 = x^3 + ax + b *1 の体  K における解全体がなす集合,すなわち
 E' = \{ (x, y) \in K \times K ; y^2 = x^3 + ax + b\}
に,無限遠点としての役割を持つ点*2  O を追加して得られる集合,
 E(K) = E' \cup O
は,Abel 群をなします.「点同士の足し算」として加法が突っ込まれた群です.この群を  K 上の楕円曲線と呼びます.足し算の構成法や Abel 群をなすことの証明に関しては,インターネットや書籍に優れた説明があるので,そちらを参照していただければと思います.

さらにまた,同じ点同士を繰り返し足すことでスカラー倍算も導入できます.すなわち,ある点 P \in E(K)に対し,
 nP = \underbrace{P + P + \cdots + P}_{n \: times}
という計算も定まります.

実数体上で考えた楕円曲線のグラフの一例を以下に示しておきます.

f:id:villach:20190317205727p:plain

ECM の手順

ECM は以下のような手順で構成されています.以下, n を実際に素因数分解したい合成数とします.以下の手順は  n の自明でない約数を求めるものなので,完全に素因数分解するには素数判定をはさみつつ再帰的に手順を実行する必要があります.

  1. 楕円曲線  E(\mathbb{Z}/n\mathbb{Z}) を適当に決め,その上の点  P をランダムに一つ定める.
  2. 適当に  k を決める.
  3.  P k 倍点である  kP を計算する. kP を計算する過程で無限遠 O に飛んでしまったら,そこから  n の非自明な約数が求まる(原理は後述).もし  kP が普通に計算できたら,1. か 2. に戻ってパラメータを選び直し,再試行する.

要は  kP を計算しているだけです. kP の計算過程で  n の非自明な約数が求まるまで,神様に祈りつつ試行を繰り返します.楕円曲線ガチャみたいなものですね.

また, k としては極めて大きな数が使用されるので,この計算にあたっては繰り返し2乗法*3などを用います.

実行結果

大きな数の取り扱いが大変だったので,Python 3 を用いて実装しました.ソースコードはチラ裏レベルのひどい代物なので,実行結果だけの記述とさせてください.

以下が実行結果の一例です.ちょっと出力がシンプルすぎる気もしますね.

f:id:villach:20190317211714p:plain

実際,29130502385925287 = 96600277 * 301557131 です.このくらいの数なら総当たりでも計算可能かもしれませんが,以下の場合はどうでしょう.

f:id:villach:20190317212029p:plain

このくらいの桁数になると,総当たりで計算するのは(少なくとも PC 使用かつ短時間では)不可能でしょう.

計算時間については,手元の PC でだいたい以下のような結果が得られています.入力に使った2つの合成数は,大きな素数2つの積で書かれる,いわば「タチの悪い」ものです.

  • 25227563887000340779(20桁)……約2秒
  • 119798122324797418809504766589(30桁)……約44秒

もっとも,ECM がかなり運ゲー色の強いアルゴリズムであること, k の選択についてあまり最適化をしていないことを考えると,もっと速くなる余地は十分あると思います.逆に,実行状況によってはもっと遅くなることも考えられます.

原理

 n が非自明な素因数  p を持っているとし,位数(要素数 p の体  \mathbb{F}_p 上の楕円曲線  E(\mathbb{F}_p) について考えます.

いま,ステップ 2. で選んだ  k が,幸運にも  E(\mathbb{F}_p) の位数の倍数となっていたとしましょう.このとき, E(\mathbb{F}_p) 上の任意の点  P は, k 倍したら必ず無限遠 O になります*4

 kP無限遠点であるということは, kP を求める式で登場する分母(仮に  d_k とします)が  \mathbb{F}_p 上で  0 となることに他なりません.いいかえると, p d_k を割り切ります.よって, p \mathrm{gcd} (d_k, n) を割り切り,わずかな例外を除いて  n の自明でない約数が得られます.

また,「 k E(\mathbb{F}_p) の位数の倍数である」という条件を満たすためにどうすればよいかを考えると, k をどう選べぶべきかもおぼろげにわかってきます.すなわち, k は約数をたくさん持つように選べばよいのです.これについては流儀が複数あるようです.

 

上述した内容からわかる通り,ECM E(\mathbb{F}_p) の構造に依拠しています.実は,ECM の前身(?)として,Pollard の  p - 1 法が存在します. p-1 法では, (\mathbb{Z}/p\mathbb{Z})^{*} の構造を利用していました.これは  p によって完全に固定されてしまうため, n の因数が「都合よく」なければ,その時点で諦めて試合終了でした.ECM は,代わりに楕円曲線  E(\mathbb{F}_p) を用いることで,仮に試行に失敗しても, E を取り換えて再チャレンジできるようにしています.これが ECM の偉大な進歩なんだそうです.

ECM では, E(\mathbb{F}_p) の位数が重要になってきますが,これについては Hasse の定理 なる定理が存在して, |\#E(\mathbb{F}_p) - p + 1| \le 2\sqrt{p} となることがわかっています.つまり,位数が  p + 1 を中心として  4\sqrt{p} の範囲に散らばっているということです.さらにまた,この「散らばり具合」に関しても 佐藤-Tate 予想という予想*5があって,そこまで偏らずいい感じに散らばっているらしいと信じられています.したがって, E(\mathbb{F}_p) の位数に望みを託す賭けも,そこまで分の悪い勝負ではないということが分かります.

今後の方針

まず,単純に実行速度を追求したいと思います.具体的には,パラメータの選択手法を洗練したり, kP の計算方法を見直したり*6といった手段が考えられます.

また,背景にある数学的理論をより深く知り,見通しの明確化を図るのも一つの目標です.

ECM の実装や理論面の学習は半分くらい高専の授業の枠内で行っているので,授業で得る知見や教員からのアドバイスも活かしていきたいですね.

参考文献

*1:Weierstrass 標準形と呼ばれます.

*2:厳密には射影幾何学を使って考えます.

*3:競プロ界隈の人にはおなじみだと思います.

*4:この辺は認識が曖昧なのですが,Lagrange の定理からしたがうそうです

*5:2019/04/30 追記:指導教員いわく,10年ほど前に証明されたそうです.勉強不足でした.

*6:繰り返し2乗法の他にも,移動窓法や符号つきm進展開法といった手法が存在するようです.