利用者:Koba-e964/特殊数体篩法

数論において、特殊数体篩法 (SNFS) は特殊用途の整数の素因数分解アルゴリズムである。一般数体篩法はこのアルゴリズムから派生したものである。

特殊数体篩法は小さい r と s を用いて r^e ± s と表せる整数に対して効率的である。(例えばメルセンヌ数など。)

ヒューリスティック的に、整数 $n$ を素因数分解するときのこのアルゴリズムの計算量は、ランダウの記号と L表記（英語版）を用いてを用いて以下の形で表せる。^[1]

\exp \left(\left(1+o(1)\right)\left({\tfrac {32}{9}}\log n\right)^{1/3}\left(\log \log n\right)^{2/3}\right)=L_{n}\left[1/3,(32/9)^{1/3}\right]

特殊数体篩法は NFSNet (有志による分散コンピューティングの取り組み) や NFS@Home などによって、Cunningham Project（英語版）の数を素因数分解するために大規模に使用されている。

しばらくの間素因数分解の記録（英語版）は特殊数体篩法によって素因数分解された数であり続けている。

概要[編集]

特殊数体篩法は、それよりももっと単純な有理篩法（英語版）に似たアイディアに基づいている。特に、特殊数体篩法に取り組むより先に有理篩法について読むと助けになるかもしれない。

特殊数体篩法は以下のように動作する。n を素因数分解したい整数とする。有理篩法と同じように、特殊数体篩法も二つのステップに分解できる。

まず、Z/nZの要素からなる因子基底の間の多数の乗法的関係を見つける。乗法的関係の個数が因子基底に含まれる要素の個数よりも多くなるようにする。
次に、これらの関係の部分集合を掛け合わせ、全ての指数が偶数となるようにし、最終的に a²≡b² (mod n) の形の合同式が得られるようにする。これによってたちどころに n の因数分解が得られる: n=gcd(a+b,n)×gcd(a-b,n)。もし正しく実行されれば、少なくとも一つのそのような因数分解は非自明である。

二番目のステップは有理篩法と同一であり、素直な線形代数の問題である。しかし一番目のステップは、数体を利用することで有理篩法とは違うより効率的（英語版）な方法で行われる。

詳細[編集]

n を因数分解したい整数とする。整数係数をもつ既約多項式 f と、f(m)≡0 (mod n) を満たす整数 m をとる。(どのように選ぶのかは次の節で説明する。) α を f の一つの根とする。これにより環 Z[α] を作ることができる。α を m に写す Z[α] から Z/nZ への環準同型がただ一つ存在する。単純性のため、Z[α] が一意分解整域であることを仮定する。このアルゴリズムはそうでない場合も動作するように修正できるが、その場合は追加の考慮事項が発生する。

次に、因子基底を二種類並列に準備する: 一つは Z[α] で、もう一つは Z で。Z[α] の因子基底は、ノルムが選択した値 $N_{\max }$ 以下であるような素イデアル全てからなる。Z の因子基底は、有理篩法と同様に、別の上界までの有理素数全てからなる。

その後、以下の条件を満たす互いに素な整数ペア (a,b) を見つける:

a+bm は Z の因子基底に関して smooth である (つまり、因子基底の要素の積である)。
a+bα は Z[α] の因子基底に関して smooth である。因子基底の選び方から、これは a+bα のノルムが $N_{\max }$ 未満の素数のみで割り切れることと同値である。

これらのペアはエラトステネスの篩と類似した篩のプロセスによって発見される。これが「数体篩法」という名前の動機付けとなっている。

こうしたペアのそれぞれに対し、a+bα の素因数分解に環準同型 φ を適用し、a+bm の素因数分解に Z から Z/nZ のカノニカルな環準同型を適用する。これらを等式で結ぶことで、Z/nZ のより大きな因子基底の要素の間の乗法的関係が得られ、もし十分な個数のペアが見つかれば上で述べたように関係を組み合わせて n を因数分解できる。

パラメータの選択[編集]

特殊数体篩法の際には、全ての数が適切な選択であるわけではない。あらかじめ適切な次数で係数が小さい多項式 f と (最適な次数は $\left(3{\frac {\log N}{\log \log N}}\right)^{\frac {1}{3}}$ であると予想されており、これは現在因数分解可能な N の大きさに対しては 4, 5, 6 である)、 $f(x)\equiv 0{\pmod {N}}$ を満たす値 x を知っている必要がある。さらにもう一つ条件がある: x は高々 $N^{1/d}$ 程度である a, b について $ax+b\equiv 0{\pmod {N}}$ を満たす必要がある。