参考文献

ysd@KLab > 因数分解 > GNFS > 参考文献

ネットで見られる(日本語)

Number Field Sieve の円分数の素因数分解への応用 (木田祐司): GNFSに詳しい。特に素元イデアルの求め方、素元イデアル分解のやり方が細かく掲載されている。
暗号技術関連の調査報告書一覧(2003年度)（情報処理推進機構）: 実際には1つ1つバラバラに紹介すべきかもしれないが、参考にすべき資料が多いので纏めて。論文を書くときにはバラバラにするから許して。
技術計算用Cプログラム (in "Tomy's Home"): 簡単な（と本人は言っている）多倍長ライブラリをCで書いている。これをC++に移植できたらオーバーロードで綺麗になって実験＆説明に便利。

ネットで見られる(英語)

An Introduction to the General Number Field Sieve (Matthew E. Briggs): GNFSの手順について基礎的な所を書いている。Virginia Polytechnic Institute and State Universityの修士論文。数学的な基礎知識は別に身につけておく必要がある。

本(日本語)

木田祐司「初等整数論」（朝倉書店） [Amazon] [OPAC]: 言葉の説明、多項式の割り算、素因子の見つけ方、因数分解…などについて詳しい。証明も載っているので手法だけで足りない人にはお勧め。

本(英語)

A.K.Lenstra,H.W.Lenstra Jr. "The development of the number filed sieve" (Springer-Verlag) [Amazon] [OPAC]: 1993年とGNFSにとっては少し古い方の本だが、様々な論文で引用されてる。東大の公的な所では数理研の図書室にしかないが、田浦先生が個人所有物として持っていたのであっさり借りれた。

計算記録

RSA200=P100･P100: 現在の世界記録。時間をかけた結果、と思っていたら効率もかなり良さそう。
C176=P87･P89: 木田祐司氏のグループが出した記録。様々なデータを惜し気も無く披露してくれている。