GNFSによる因数分解具体例

    2006/03/20 早稲田大学 後 保範 (Waseda University, Ushiro Yasunori )
    2006/11/13 具体例の誤り指摘により改定

0. はじめに

 具体的GNFSの計算手順を教えて頂いた立教大学 木田祐司教授に謹んで感謝の意を表します。

1. GNFSによる篩の具体例

 3次多項式を使用したGNFSによる篩部分(篩を含む全体)の GNFS篩例
 GNFSの篩部分をより詳しく記載したもので、篩以降を含めた素因数分解は因数分解の具体例を参照。

2. GNFSによる因数分解の具体例

  イデアル(多項式)の平方根の計算は、一般に使用されている方法は複雑なため、連立非線形
 方程式に準ニュートン法を使用する方式で示す。10進200桁のRSA暗号のGNFSによる解読はπ計算
 に換算すると数兆桁の計算に対応する。一方、同じ計算のイデアルの平方根を連立非線形方程式
 にすると、高々数百億桁であり、同じ桁数のπ計算に対応する。このため、数学的に複雑な方法
 より非線形方程式を解く方がより頑丈なプログラムになるはずである。非線形方程式を解くと
 整数でない解も求まるが、そちらは捨て整数となる数値解を求める。

 3次多項式を使用したGNFSによる因数分解(篩を含む全体)の GNFS因数分解例