数体篩法(概要)

ysd@KLab > 因数分解 > GNFS > 数体篩法

名前

"General Number Field Sieve"の頭文字を取ってGNFSと呼ぶ。単語を直訳しても一般数体篩法にしかならない。アインシュタインの相対性理論のように、一般があれば特殊もあるということで、そちらは"Special Number Field Sieve"の略でSNFSと呼ばれる。勿論和名は特殊数体篩法。

で、何すんのさ？

因数分解。注意して欲しいのは「素因数分解」ではないということ。なので主目的は、馬鹿でかい素数二つを掛け合わせてできた合成数を分解するとか、とりあえず大きな数を小さな{素数or合成数}の積に分解するとかいうこと。130桁以上の数を同じサイズの2つの数に分けるのは多分一番速い。

まずは流れを教えてよ

  1. 多項式を作る
  2. 沢山の(a,b)をそれぞれ整数体、代数体の2数体で分解する
  3. 上手く(a,b)を組み合わせる。条件はφ(β2)≡y2 (mod n)
  4. GCD(φ(β)-y,n)を計算して結果が出ればOK

意味が分かりません

そりゃそうです。1つ1つをプログラムが組める/手計算できるレベルで解説すると1MBでも足りません。

補足しなさいよ

別項目になっていないことで必要な説明を思いついたら書きます。