Loading AI tools
来自维基百科,自由的百科全书
在數論中,普通數域篩選法(GNFS)是已知效率最高的分解整數的算法。
分解整數n(由⌊log2 n⌋ + 1個位元組成)需要
![]() |
此條目需要擴充。 (2013年9月28日) |
步(參見L符號)。它是從特殊數域篩選法引申出來的。
如果條件數域篩沒有限定條件,就是指普通數域篩選。
我們選擇兩個不可約分的最高次項為d和e的兩個多項式f(x)和g(x),
令通根m是f和g mod n的根;則他們會是m階,同時次項d 和 e比較低。
選擇最高次項為d和e的兩個多項式f(x)和g(x),它們具有整數係數,在有理數上不可約,並且在mod n時具有共同的整數根m。
選擇這些多項式的最佳策略尚不明確。
一種簡單的方法是為多項式選擇一個次數d,考慮n^(1/d)的多個不同m(允許在-m和m之間的數字),
並選擇f(x)作為係數最小d 且 g(x)為 x − m的多項式。
考慮數字環Z [r1]和Z [r2],其中r1和r2是多項式f和g的根。
由於f為d次且具有整數係數,因此如果a和b為整數,則(b^d)·f(a / b)也將為r,我們將其稱為r。
類似地,s = (b^e)·g(a / b)是整數。目的是找到a和b的整數值,
這些整數值同時使r和s相對於所選質數的底數平滑。
如果a和b小,則r和s也將小,大約為m的大小,並且我們有更好的機會使它們同時平滑。
具有足夠多的數對(r,s),使用高斯消去法,可以同時使某些r和相應s的乘積成為平方。
需要一個稍微強一些的條件-它們是數字中的平方範數,但是該條件也可以通過此方法來實現。
每個r都是a-r1b的範數,因此相應因子a-r1b的乘積是Z [r1]中的平方,
類似地,因子a-r2b的乘積是Z [r2]中的平方,並且也可以計算出「平方根」。
應該指出的是,使用高斯消去法不能給出算法的最佳運行時間。取而代之的是使用稀疏矩陣求解算法,例如Block Lanczos或Block Wiedemann。
由於m是f和g mod n的根,因此從環Z [r1]和Z [r2]到環Z / nZ(整數mod n)存在同態,它們將r1和r2映射到m,並且這些同態將把每個「平方根」(通常不表示為有理數)映射為其整數表示。
現在,可以通過兩種方式將因子a-mb mod n的乘積作為一個平方來獲得-每個同態一種。
因此,可以找到兩個數字x和y,其中x^2- y^2被n整除,
並且又有可能至少有一半通過找到n和x-y的最大公約數而得到。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.