楕円曲線法（ECM） - yōsei.fi ［妖精現実 フェアリアル］

楕円曲線で因数分解 2016年 8月14日 記事ID e60814 楕円曲線を使って、巨大整数に含まれる数十桁の因数を検出できる。計算は、曲線上の勝手な点を選んで整数倍するだけ。 楕円曲線法ステージ2は、モンゴメリー、ブレント、日本のスヤマが開拓した面白い領域だが、一般向けの解説（教科書やウェブの記事）があまりない。出発点となるレンストラーのステージ1と、その先にあるモンゴメリー形式、標準版ステージ2、素数ペアリングについて整理してみた。前提として、中学数学の知識を仮定する。 背景と原理 §1 楕円曲線法の前夜 §2 楕円曲線法の仕組み §3 楕円曲線プチ入門 §4 楕円曲線法の実際 実装と高速化 §5 モンゴメリーの計算法 §6 楕円曲線法ステージ2 §7 ステージ2の実装例 付録A: 補足説明 付録B: ソースコード 参考文献 更新履歴 §1 楕円曲線法の前夜 20世紀後半まで「整数を