查看“︁普通数域筛选法”︁的源代码

{{Copy edit|time=2022-06-09T14:54:24+00:00}}
{{expand|time=2013-09-28T11:41:12+00:00}}
在数论中，'''普通数域筛选法'''（GNFS）是已知的效率最高的[[整数分解|分解整数]]的算法。<br>
分解整数''n''（由{{math|⌊log<sub>2</sub> {{mvar|n}}⌋ + 1}}个位元组成）需要 

:<math>\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]</math>

此步（参见[[L符號|L符号]]），它是从{{link-en|特殊数域筛选法|Special number field sieve}}引申出来的。<br>
如果条件''数域筛''没有限定条件，就是指普通数域筛选。

== 方法 ==

我们选择两个不可约分的最高次項為d和e的兩個[[多项式]]''f(x)''和''g(x)''，<br>
令通根'''m'''是f和g mod n的根；则他们会是''m''阶，同时次項''d'' 和 ''e''比较低。<br>

選擇最高次項為d和e的兩個多項式f（x）和g（x），它們具有整數係數，在有理數上是不可約的，並且在mod n時具有共同的整數根m。<br>
選擇這些多項式的最佳策略尚不明確。<br>
一種簡單的方法是為多項式選擇一個次數d，考慮n^(1/d)的多個不同m（允許在-m和m之間的數字），<br>
並選擇f（x）作為係數最小d 且 g（x）為 x − m的多項式。

考慮數字環Z [r1]和Z [r2]，其中r1和r2是多項式f和g的根。<br>
由於f為d次且具有整數係數，因此如果a和b為整數，則(b^d)·f（a / b）也將為r，我們將其稱為r。<br>
類似地，s ＝ (b^e)·g（a / b）是整數。目的是找到a和b的整數值，<br>
這些整數值同時使r和s相對於所選質數的底數平滑。<br>
如果a和b小，則r和s也將小，大約為m的大小，並且我們有更好的機會使它們同時平滑。

具有足夠多的數對(r,s)，使用[[高斯消去法]]，可以同時使某些r和相應s的乘積成為平方。<br>
需要一個稍微強一些的條件-它們是數字中的平方範數，但是該條件也可以通過此方法來實現。<br>
每個r都是a-r1b的範數，因此相應因子a-r1b的乘積是Z [r1]中的平方，<br>
類似地，因子a-r2b的乘積是Z [r2]中的平方，並且也可以計算出“平方根”。<br>
應該指出的是，使用高斯消去法不能給出算法的最佳運行時間。取而代之的是使用稀疏矩陣求解算法，例如Block Lanczos或Block Wiedemann。
<br>

由於m是f和g mod n的根，因此從環Z [r1]和Z [r2]到環Z / nZ（整數mod n）存在同態，它們將r1和r2映射到m，並且這些同態將把每個“平方根”（通常不表示為有理數）映射為其整數表示。<br>
現在，可以通過兩種方式將因子a-mb mod n的乘積作為一個平方來獲得-每個同態一種。<br>
因此，可以找到兩個數字x和y，其中x^2- y^2被n整除，<br>
並且又有可能至少有一半通過找到n和x-y的最大公約數而得到。

== 参见 ==
{{Portal|数学}}
*[[整数分解]]

== 参考 ==

* Lenstra, Arjen K.; Lenstra, H.W. Jr. (Eds.) (1993). ''The development of the number field sieve''. Lecture Notes in Math. 1554. Springer-Verlag.

* Pomerance, Carl (1996). [http://www.ams.org/notices/199612/pomerance.pdf A Tale of Two Sieves] {{Wayback|url=http://www.ams.org/notices/199612/pomerance.pdf |date=20201111201448 }}。''Notices of the AMS'' 1996, 1473–1485.

* Richard Crandall and [[Carl Pomerance]]. Prime Numbers: A Computational Perspective (2001). 2nd edition, Springer. {{ISBN|0-387-25282-7}}. Section 6.2: Number field sieve, pp.&nbsp;278–301.

[[Category:整数分解算法]]