一般数体篩法

ウィキペディア

一般数体篩法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/06/26 09:58 UTC 版)

数論において、一般数体篩法（いっぱんすうたいふるいほう、英: General number field sieve, GNFS）は、10¹⁰⁰より大きい整数を素因数分解する古典的アルゴリズムであり、現在知られている最も効率的（英語版）なものである^[1]。ヒューリスティックに、整数 n （ ⌊log₂ n⌋ + 1 ビットで構成される）を素因数分解するための複雑性は、L表記（英語版）(L-notation)を用いて以下のように表される^[2]。

${\displaystyle \exp \left(\left({\sqrt[{3}]{\frac {64}{9}}}+o(1)\right)(\ln n)^{\frac {1}{3}}(\ln \ln n)^{\frac {2}{3}}\right)=L_{n}\left[{\frac {1}{3}},{\sqrt[{3}]{\frac {64}{9}}}\right]}$