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

特殊用途の整数因数分解アルゴリズム

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

特殊数体ふるいは、r ^e ± sという形式の整数（ rとsは小さい）（たとえばメルセンヌ数）に有効です。

経験的に、整数を因数分解する複雑さは次のようになります。^[1] $n$

\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の因数分解、すなわちn = gcd ( a + b , n )×gcd( a - b , n ) に直結します。正しく行えば、少なくとも1つの因数分解は非自明になることはほぼ確実です。

2番目のステップは有理ふるいの場合と同一であり、単純な線形代数問題です。しかし、最初のステップは有理ふるいとは異なり、数体を利用することでより効率的な方法で実行されます。

方法の詳細

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

次に、 Z [ α ] とZにそれぞれ 1つずつ、 2 つの平行な因数基底を設定します。 Z [ α ]の因数基底は、Z [ α ] 内の、ノルムが特定の値で制限されるすべての素イデアルから構成されます。 Z内の因数基底は、有理ふるいの場合と同様に、他の制限値までのすべての素整数から構成されます。 $N_{\max }$

次に、次のように互いに素な整数のペア ( a、b )を検索します。

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

これらのペアは、エラトステネスのふるいに類似したふるい分けのプロセスを通じて見つかります。これが「数体ふるい」という名前の由来です。

このような各ペアについて、環準同型 φ をa + bαの因数分解に適用することができ、ZからZ /n Zへの標準環準同型をa + bmの因数分解に適用することができます。これらを等しくすると、 Z /n Zのより大きな因数基数の元の間に乗法関係が与えられます。十分な数のペアが見つかった場合、上記のように、これらの関係を結合してnを因数分解することができます。

パラメータの選択

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

このような多項式が存在する数値セットの 1 つは、カニンガムテーブルの数です。たとえば、NFSNET が⁠ ⁠を因数分解したとき、 ⁠ ⁠、およびであるため、⁠ ⁠を含む多項式⁠ ⁠を使用しました。 $a^{b}\pm 1$ $3^{479}+1$ $x^{6}+3$ $x=3^{80}$ $(3^{80})^{6}+3=3^{480}+3$ $3^{480}+3\equiv 0{\pmod {3^{479}+1}}$

フィボナッチ数やルーカス数など、線形回帰で定義される数にもSNFS多項式は存在しますが、これらの構築は少し複雑です。例えば、は多項式を持ち、 xの値はを満たします。^[2] $F_{709}$ $n^{5}+10n^{3}+10n^{2}+10n+3$ $F_{142}x-F_{141}=0$

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

アルゴリズムの限界

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

参照

一般数体ふるい

参考文献

^ ポメランス、カール（1996年12月）、「二つのふるいの物語」（PDF）、AMSの通知、第43巻、第12号、 1473～ 1485ページ
^ Franke, Jens. 「ggnfs-lasieve4のインストールノート」. MITマサチューセッツ工科大学.

さらに詳しい情報

バーンズ、スティーブン（2005年5月18日）、「数体ふるい」（PDF）、数学129 、 2006年9月20日時点のオリジナル（PDF）からアーカイブ、 2005年9月5日閲覧
レンストラ, AK ;レンストラ, HW Jr. ; マナッセ, MS & ポラード, 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
レンストラ, AK; レンストラ, HW Jr.編 (1993)、『数体ふるいの開発』、数学講義ノート、第1554巻、ニューヨーク：シュプリンガー・フェアラーク、ISBN 978-3-540-57013-4
シルバーマン、ロバート・D. (2007)、「SNFSの最適パラメータ化」、数学暗号学ジャーナル、1 (2): 105– 124、CiteSeerX 10.1.1.12.2975、doi :10.1515/JMC.2007.007、S2CID 16236028

[1] ポメランス、カール（1996年12月）、「二つのふるいの物語」（PDF）、AMSの通知、第43巻、第12号、 1473～ 1485ページ

[2] Franke, Jens. 「ggnfs-lasieve4のインストールノート」. MITマサチューセッツ工科大学.