」と言い換えることができる。モンゴメリーの方法で割り算を先延ばししている場合には、実質的に計算不能に陥っていても、見掛け上は計算を続行できる。乗法逆元を持たないと困る」ということ。考えれば)話は丸く収まる。頑張っても体にならない。これが「計算不能」の核心だろう。楕円曲線法の目的は達成される。それが楕円曲線法の舞台になる。考えれば、それは群になる。おける演算は「ほぼ同型」。側で和が定義されないが、そのときには探している因数が分かり、因数分解に成功する。上で)計算が行われる。群ではないので点の足し算ができる保証はなく、数学的には暴挙だが、「計算不能になったら探している因数が判明する」という特性のため、実用上、暴挙が正当化される。演算を行っている」と解釈できる。この解釈なら、数学的にもほぼ問題ないだろう。対する掛け算は、1個の曲線につき1回で済ませている。そのまま計算している。大きな数になり、メモリー不足になったり動作が緩慢になったりする恐れがある。明示的に計算した方が速いようだ。計算しておいて、それを全部の曲線に対して使い回せる。これがプラスに作用するのだろう。明示的に計算する必要はないと示唆しているが、当時と現在ではメモリー環境が全く違い、議論の前提が異なる。x-座標より桁違いに大きいため、かえって計算量が増えてしまう)。明示的に計算するうまみは少ない(キャッシュしても使い回せないので)。可能であるかのように扱っている(同253ページ)。満たされないと思われる。満たさないペアが生成される可能性がある。生成するペア数の正確なカウントではある)。形で書かれることになり、選択の余地がない。ある程度大きいことが必要だ。正常動作しないという事実は、実用上問題にならない(ペアリングによる高速化という観点からは、仮に正常動作するとしても、その設定を使う意味がない)。変えれば問題は消滅する。ソースコードhttp://www.faireal.net/demo/TinyBigInt/この記事の初版(2016年8月14日)では以下が使われた。任意精度整数演算ライブラリ、バージョン0.3(2016年8月7日版)。本文で紹介されている全部のコードを含む(2016年8月14日版)。呼び出しの大部分は、初期状態ではコメントアウトされている。試したい部分について1回に1個だけコメントアウトを外し、実行後またコメントアウトするといいだろう。テスト環境において1分以上かかるデモもある。遅い環境(ある種のブラウザなど)では、何十分もかかる場合があるので注意。本文(テキスト・画像)とソースは、全てパブリックドメイン。バージョン2を公開した。毎回ループ内で計算していた。新バージョンでは、これをループに入る前に1回だけ計算するように改めた。それ以外に実質的な変更はない。本文中のコードも同様に更新(詳細)。付属ソースコード内の関数。本文で述べた方法を基に「メルセンヌ数に対するプチ楕円曲線法」を行う。第3引数以降は省略可能(省略された場合、デフォルト値が使われる)。9083095717429111383669040079371492978878426527800970.4秒で分解された。楕円曲線を持ち出すまでもない小さい素因数だが、これはただのテスト。問題は、この余因数の分解だ。14732265321145317331353282383ラッキー・シグマは121。検出された23桁の因数と余因数は、いずれも素数。所要時間は4分20秒だった(モード2では4分19秒)。粘れば分解に成功する(所要時間3分45秒)。第3因数(27桁)を検出。4027澗(かん)台の因数(40桁)が検出された(2016年7月27日)。別の方法でラッキー・シグマを調べてそこを狙い撃ちするチートだが、動作の検証のために実行。真面目に検索しても48時間以内に成功しそうだ。ブレントによる楕円曲線法の初期論文(初版1985年9月、1985年12月改訂、1986年掲載、1998年再版)。「誕生日パラドックス」版ステージ2を提案している。モンゴメリーの論文(初版1985年12月、1986年7月改訂、1987年1月掲載)。1」法、楕円曲線法などを統一的に扱い、ステージ2の高速化について論じている。この記事の後半の実装の大部分は、これに基づく。楕円曲線法の発見者ヘンドリク・レンストラー自身による記念碑的論文(1986年9月提出、1987年掲載)。発見者が正式発表する前に、別の人々が「どうやってそれを発展させるか」を提案した。第一発見者がレンストラーであることには変わりない。1986年5月のバージョンもある(*)。レンストラー自身による別の論文(日付は1986年7月)。楕円曲線法を厳密に扱おうとすると、有限環上の楕円曲線が問題になる。その理論をあえて追究しない立場だが、こちらではこの問題に取り組んでいる。ステージ2のバリエーションについての詳細なコメントを含む。楕円曲線法の発見から十数年でどのような発展があったのか、実践的観点から書かれている。楕円曲線法の発見から2006年までの約20年間において、どのようなアルゴリズムの発展があったか概観している。シンプルなステージ2の疑似コードを含む。ステージ2入門となり得る。楕円曲線法の話になる。この記事の前半の内容について、数学的観点から分かりやすく記されている。明快な標準形ステージ1入門。公開されていて、誤植なども随時修正・更新されている。メルセンヌ・ウィキの記事。導入部は「超入門」で対象読者が異なるが、その先では最短距離でモンゴメリーの計算法を導入している。もったいぶらずに実践的。モンゴメリー形式のステージ1入門となり得る。ステージ2の話が断りなくアフィン座標になっているので注意。ウィキペディアの記事。内容は実質的に標準形ステージ1だけだが、アフィン座標と射影座標の両方で記述されている。いう独立した記事がある。標準形のステージ1を扱った日本語の教科書もいくつかある。今回資料として使ったわけではなく、このような場所で間接的に宣伝するスタイルを好まないので、具体的な題名・出版社名などは書かないけれど、目次を見て「楕円曲線を使った因数分解」というようなセクションがあれば、たぶんステージ1の紹介だろう。ある(下記「追加の参考文献」参照)。ポーランド語などとなって、ますます読むのが大変になる。いるとも思えず、メルセンヌ・ウィキに英語で書いた方が、より多くの人に役立って社会貢献になるかもしれない。いえ、多様性も大切だろう。ついての日本語の資料(ウェブ上で自由に読めるもの)としては、現在(2016年)これが最良かもしれない。素数ペアリングを別にすれば、この記事で取り上げた話題のほとんど全てが、簡潔に解説されている。ステージ2のバリエーションの説明を含む。これは、モンゴメリーの計算法(XZ座標)の一般化に当たる。間の素数を抜き出して利用する。伊豆が紹介している「モンゴメリーのステージ2」は、それとは異なるバリエーション。コンピューター科学の専門家と著名な数論学者により、共同執筆された本。理論の簡略な説明と、多くの疑似コードから成る。ステージ1・ステージ2の紹介を含む。ステージ2の実装では、素数の間隔を利用するシンプルなアルゴリズムをベースに、高速化が行われている。楕円曲線「暗号」と楕円曲線「法」は分野が違うが、入り口は共通。それが丁寧に解説されている。環境によっては文字化けするが、ファイルの中身は問題なく表示できた。このコースは、実装を視野に入れつつも「実用上動けばいい」というのではなく、数学的厳密性を重視しているようだ。ような貴重なヒントがいろいろ書かれている。最新(2010年代)の成果も紹介されている。最初に読む入門としては深過ぎるかもしれないが、文章は気さくで明快。以下が楕円曲線法ステージ1。モンゴメリー曲線・モンゴメリーの計算法について詳しく説明されている。PDF)には、ステージ2に関する理論が含まれている。モンゴメリー形式を使ったステージ1とステージ2について、実装の細部にまで踏み込んで考察・実践している。ステージ2の「赤ちゃん・巨人」では、素数判定をせず全部掛け算する作戦を使っている。スヤマのアイデアとその発展について、明晰な文章で論じている。学生が書いた実験レポート。実装は示されていないが、スヤマ系の実験を行っている。エドワーズ曲線(比較的新しい話題)に言及している。