特殊番号フィールドふるい

数論という数学の一分野において、特殊数体篩（SNFS）は、特定の目的に特化した整数因数分解アルゴリズムである。一般数体篩（GNFS）は、このSNFSから派生したものである。

特殊な数体篩は、 r ^e ± sの形の整数に対して効率的です。ここで、rとsは小さいです (たとえば、メルセンヌ数)。

経験的に、整数を因数分解する複雑さは${\displaystyle n}$形式は次のとおりです。^{[ 1 ]}

${\displaystyle \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]}$

O表記とL表記で。

SNFSは、NFSNet（ボランティアによる分散コンピューティングプロジェクト）、NFS@Homeなどで、 Cunninghamプロジェクトの数値を因数分解するために広く利用されてきました。しばらくの間、整数因数分解の記録はSNFSによって因数分解された数値でした。

SNFSは、はるかに単純な有理数篩と同様の考え方に基づいています。特に、読者はSNFSに取り組む前に、まず有理数篩について読んでおくと役立つでしょう。

SNFSは次のように機能します。nを因数分解したい整数とします。有理数篩と同様に、SNFSは2つのステップに分けられます。

• まず、 Z / n Zの要素からなる因数基底の中で、乗法関係の数が因数基底の要素数よりも多くなるような乗法関係を多数見つけます。
• ^{次に、これらの関係のサブセットを、すべての指数}が偶数になるように掛け合わせると、a²≡b²（mod n）の形の合同式が得られます。これらは、n = gcd ( a + b , n ) × gcd( a - b , n ^)というnの因数分解にすぐにつながります。正しく行えば、少なくとも1つの因数分解が非自明なものになることはほぼ確実です。

第２のステップは有理数篩の場合と全く同じで、単純な線形代数の問題です。しかし、第１のステップは、数体を利用することで、有理数篩とは異なる、より効率的な方法で行われます。

因数分解したい整数をnとします。整数係数を持つ既約多項式fと、 f ( m ) ≡ 0 ( mod n )となる整数mを選びます(これらの選び方は次のセクションで説明します)。α をfの根とします。すると、環Z [ α ]を形成できます。Z [ α ]からZ /n Zへの環準同型φ は一意に存在し、α をmに写像します。簡単のため、 Z [ α ] は一意の因数分解領域であると仮定します。そうでない場合でもアルゴリズムを修正して動作させることはできますが、その場合はさらにいくつかの複雑な問題が生じます。

次に、 Z [ α ]とZの2つの並列因子基底を設定します。Z [ α ]の因子基底は、ノルムが選択された値で制限されるZ[α]のすべての素イデアルから構成されます。${\displaystyle N_{\max }}$有理数篩の場合と同様に、 Zの因数基底は、ある上限までのすべての素数から構成される。

次に、以下の条件を満たす互いに素な整数のペア ( a , b )を探します。

• a + bmはZの因子基底に関して滑らかである（つまり、因子基底の要素の積である）。
• a + b αはZ [ α ]の因子基底に関して滑らかです。因子基底の選択方法を考慮すると、これはa + b αのノルムが1 未満の素数でのみ割り切れることと同等です。${\displaystyle N_{\max }}$。

これらのペアは、エラトステネスの篩に類似したふるい分けの過程を経て見つけ出されます。これが「数体篩」という名前の由来です。

このような各ペアに対して、 a + b αの因数分解に環準同型φ を適用し、a + bmの因数分解にZからZ /n Zへの標準環準同型を適用できます。これらを等しいと置くと、Z /n Zのより大きな因数基底の要素間に乗法関係が得られ、十分な数のペアが見つかれば、上記のように関係を組み合わせてnを因数分解することができます。

すべての数がSNFSに適した選択肢となるわけではない。適切な次数を持つ多項式fを事前に知っておく必要がある（最適な次数はと推測されている）。$\displaystyle \left(3\frac{\log N}{\log \log N}}\right)^{\frac{1}{3}}}$（現在因数分解可能な N のサイズに対して 4、5、または 6 ）小さな係数と、次の値x を持つ。${\displaystyle f(x)\equiv 0{\pmod {N}}}$ここでNは因数分解する数である。追加条件として、xは以下を満たさなければならない。${\displaystyle ax+b\equiv 0{\pmod {N}}}$aとbが以下${\displaystyle N^{1/d}}$。

このような多項式が存在する数値の集合は、${\displaystyle a^{b}\pm 1}$カニンガム表からの数値。例えば、NFSNETが因数分解したとき${\displaystyle 3^{479}+1}$⁠、彼らは多項式を使用しました${\displaystyle x^{6}+3}$⁠と共に⁠${\displaystyle x=3^{80}}$⁠、以来⁠${\displaystyle (3^{80})^{6}+3=3^{480}+3}$⁠、そして${\displaystyle 3^{480}+3\equiv 0{\pmod {3^{479}+1}}}$。

フィボナッチ数やルーカス数など、線形漸化式で定義される数もSNFS多項式を持ちますが、これらは構成するのが少し難しくなります。例えば、${\displaystyle F_{709}}$多項式を持つ${\displaystyle n^{5}+10n^{3}+10n^{2}+10n+3}$、そしてxの値は以下を満たす。${\displaystyle F_{142}x-F_{141}=0}$[ ^{2 ]​}

SNFSと互換性のある大きな数の因数が既に分かっている場合は、残りの部分を法としてSNFS計算を行うことができます。上記のNFSNETの例では、${\displaystyle 3^{479}+1=(2^{2}\times 158071\times 7167757\times 7759574882776161031)}$197桁の合成数（小さな因数はECMによって見つけられた）を乗じ、SNFSは197桁の数を法として実行されました。SNFSに必要な関係の数は依然として大きな数の大きさに依存しますが、個々の計算は小さな数を法としてより速く行われます。

前述のように、このアルゴリズムは、rとsが比較的小さい形式のr ^e ± sの数に対して非常に効率的です。また、係数が小さい多項式として表現できる任意の整数に対しても効率的です。これには、より一般的な形式のar ^e ± bs ^fの整数や、バイナリ表現のハミング重みが低い多くの整数も含まれます。その理由は次のとおりです。数体篩法は、2 つの異なる体で篩い分けを実行します。最初の体は通常、有理数です。2 番目は、より高次の体です。アルゴリズムの効率は、これらの体の特定の要素のノルムに大きく依存します。整数が係数が小さい多項式として表現できる場合、発生するノルムは、整数が一般的な多項式で表現される場合に発生するノルムよりもはるかに小さくなります。その理由は、一般的な多項式ははるかに大きな係数を持ち、それに応じてノルムも大きくなるためです。このアルゴリズムは、固定された素数の集合上でこれらのノルムを因数分解しようとします。ノルムが小さいほど、これらの数は因数分解される可能性が高くなります。

• 一般番号フィールドふるい

• スティーブン・バーンズ（2005年5月18日）「数体篩」（PDF）、Math 129 、 2006年9月20日にオリジナル（PDF）からアーカイブ、 2005年9月5日取得
• Lenstra, AK ; Lenstra, HW Jr. ; Manasse, MS & Pollard, JM (1993)、「第 9 項フェルマー数の因数分解」、Mathematics of Computation、61 (203): 319–349、Bibcode : 1993MaCom..61..319L、doi : 10.1090/S0025-5718-1993-1182953-4、hdl : 1887/2150
• Lenstra, AK; Lenstra, HW Jr. 編 (1993) 『数体篩の発展』、Lecture Notes in Mathematics、第 1554 巻 、ニューヨーク: Springer-Verlag、ISBN 978-3-540-57013-4
• Silverman, Robert D. (2007)、「SNFSの最適パラメータ化」、Journal of Mathematical Cryptology、1 (2): 105–124、CiteSeerX 10.1.1.12.2975、doi : 10.1515/JMC.2007.007、S2CID 16236028