著者

青木 和麻呂

出版者

一般社団法人情報処理学会

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.51, no.8, pp.1030-1038, 2010-08-15

参考文献数

6

---

2009年12月12日(日本時間では13日),RSA-768と呼ばれる768ビットの合成数が素因数分解された.特別な形の合成数では以前に,より大きいものが素因数分解されているが,RSA公開鍵暗号に利用される大きな2素数の積の素因数分解に対しては,世界記録更新である.この記録は瑞,日,独,仏,蘭の5カ国の機関の研究者の共同作業の成果であり,筆者もこの作業に参加した.この素因数分解では,一般数体篩法(いっぱんすうたいふるいほう; GNFS)と呼ばれる代数的整数論を応用した方法が使われた.数体篩法を実際に実現するためには,概念的なアルゴリズムばかりではなく,細部の実装や計算資源の配分などが効率の重要な鍵を握っている.本稿では,数体篩法の概略を説明し,各ステップでの実装や計算機運用の問題点を紹介する.最後に,従来よりRSA公開鍵暗号で1024ビットの公開鍵の新規利用は推奨できないことが指摘されていたが,今回768ビットの合成数が現実に素因数分解されたことはこの指摘を補強するものであることを付け加えておく.