本页使用了标题或全文手工转换

AKS質數測試

维基百科,自由的百科全书
跳转至: 导航搜索

AKS質數測試(又被稱為Agrawal–Kayal–Saxena質數測試Cyclotomic AKS test)是一個決定型質數測試演算法 ,由三個來自印度坎普爾理工學院英语Indian Institute of Technology Kanpur的計算機科學家,Manindra Agrawal英语Manindra AgrawalNeeraj Kayal英语Neeraj KayalNitin Saxena英语Nitin Saxena,在2002年8月6日發表於一篇題為質數屬於P的論文。[1]作者們因此獲得了許多獎項,包含了2006年的哥德爾獎和2006年的Fulkerson Prize英语Fulkerson Prize。這個演算法可以在多項式時間之內,決定一個給定整數是質數或者合數

重要性[编辑]

AKS最關鍵的重要性在於它是第一個被發表的一般的多項式的確定性的無仰賴的質數判定算法。先前的算法至多達到了其中三點,但從未達到全部四個。

  • AKS算法可以被用於檢測任何一般的給定數字是否為質數。很多已知的高速判定算法只適用於滿足特定條件的質數。例如,卢卡斯-莱默检验法僅對梅森質數適用,而Pépin測試僅對費馬數適用。
  • 算法的最長運行時間可以被表為一個目標數字長度的多項式ECPPAPR能夠判斷一個給定數字是否為質數,但無法對所有輸入給出多項式時間範圍。
  • 算法可以確定性地判斷一個給定數字是否為質數。隨機測試演算法,例如米勒-拉宾检验Baillie–PSW,可以在多項式時間內對給定數字進行校驗,但只能給出概率性的結果。
  • AKS算法並未“仰賴”任何未證明猜想。一個反例是确定性米勒检验:該算法可以在多項式時間內對所有輸入給出確定性結果,但其正確性卻基於尚未被證明的廣義黎曼猜想

概念[编辑]

AKS 質數測試主要是基於以下定理:整數n (≥ 2)是質數,若且唯若

 (x - a)^{n} \equiv (x^{n} - a) \pmod{n} \qquad (1)

這個同餘多項式對所有與n互質的整數a均成立。 這個定理是費馬小定理的一般化,並且可以簡單的使用二項式定理二項式係數的這個特徵:

 {n \choose k} \equiv 0 \pmod{n} ,對任何 0<k<n ,若且唯若 n 是質數

來證明出此定理。

雖然說關係式 (1) 基本上構成了整個質數測試,但是驗證花費的時間卻是指數時間。因此,為了減少計算複雜度, AKS改為使用以下的同餘多項式:

 (x - a)^{n} \equiv (x^{n} - a) \pmod{n, x^{r} - 1} \qquad (2)

這個多項式與

 存在多項式 fg,令:(x - a)^n - (x^n - a) = nf + (x^r - 1)g \qquad (3)

意義是等同的。

這個同餘式可以在多項式時間之內檢查完畢。這裡我們要注意所有的質數必定滿足此條件式 (令 g = 0 則 (3) 等於 (1),因此符合 n 必定是質數)。 然而,有一些合數也會滿足這個條件式。有關AKS正確性的證明包含了推導出存在一個夠小的r以及一個夠小的整數集合A,令如果此同餘式對所有A裡面的整數都滿足,則n必定為質數。

歷史以及運算時間[编辑]

在上文引用的論文的第一版本中,作者們證明了算法的漸近時間為Õ(\log^{12}(n))。換言之,算法使用少於n的數字長度的十二次方乘以一個(數字長度的)多重對數。但是,論文證明的時間上界卻過於寬鬆;事實上,一個被普遍相信的關於索菲熱爾曼質數分佈的假設如果為真,則會立即將最壞情況減至Õ(\log^6(n))

在這一發現後的幾個月中,新的變體陸續出現(Lenstra 2002, Pomerance 2002, Berrizbeitia 2003, Cheng 2003, Bernstein 2003a/b, Lenstra和Pomerance 2003)並依次提高了算法的速度(以改進幅度為序)。由於這些變體的出現,Crandall和Papadopoulos在其科學論文“AKS-類質數測試的實現”(2003年三月發表)中將其稱為算法的“AKS-類”。

出於對這些變體和其他回复的回應,論文“質數屬於P”稍後被進行了更新,新版本包括了一個AKS算法的正規公式化表述和其正確性證明。(這一版本在Annals of Mathematics上發表。)雖然基本思想沒有變化,r卻被採用了新方法進行選擇,而正確性證明也變得更加緊緻有序。與舊證明依賴於許多不同的方法不同,新版本幾乎只依賴於有限域上的分圓多項式的特徵。新版本同時也優化了時間複雜度的邊界到Õ(\log^{10.5}(n))。通過篩法獲得的其他結果可以將其進一步簡化到Õ(\log^{7.5}(n))

在2005年,Carl PomeranceH. W. Lenstra, Jr.展示了一個AKS的變體,可以在Õ(log6(n))次操作內完成測試(n是被測試數)。對於原算法的Õ(log12(n))邊界而言,這是一個顯著的改進。[2]

演算法[编辑]

整個演算法的操作如下:[1]

輸入:整數 n > 1
  1. 若存在整數a > 0 且b > 1 ,令 n = ab ;則輸出合數
  2. 找出最小的 rordr(n) > log22(n).
  3. 若 對某些ar,1 < gcd(a,n) < n,輸出合數。(gcd是指最大公因數)。
  4. nr, 輸出質數
  5. a = 1 到 \scriptstyle\lfloor \scriptstyle\sqrt{\varphi(r)}\log(n) \scriptstyle\rfloor的所有數,
    如果 (X+a)nXn+a (mod Xr − 1,n), 輸出合數
  6. 輸出 質數

這裡的 ordr(n)是n mod r的阶。 另外,這裡的log 代表以二為底的對數,\scriptstyle\varphi(r)則是r歐拉函數

下面說明若n是個質數,那麼算法總是會返回質數:由於n是質數,步驟1和3永遠不會返回合數。步驟5也不會返回合數,因為(2)對所有質數n為真。因此,算法一定會在步驟4或6返回質數

對應地,如果n是合數,那麼算法一定返回合數:如果算法返回質數,那麼則一定是從步驟4或6返回。對於前者,因為nrn必然有因子ar符合1 < gcd(a,n) < n,因此會返回合數。剩餘的可能性就是步驟6,在文章[1]中,這種情況被證明不會發生,因為在步驟5中檢驗的多個等式可以確保輸出一定是合數

具体实现[编辑]

欧几里得算法求最大公约数:GCD(a,b)

  1. 如果b=0
    输出 a
  2. 输出 GCD(b,a\,\bmod\,b)


判定n(奇数)是否为平方数:N_2(n)

  1. 如果n \equiv 2 \pmod{3}
    输出False
  2. 计算 l =\left \lceil \frac{1}{2} \log_3(n) \right \rceil
  3. 计算 r =\left \lfloor \ \log(l) \right \rfloor
  4. g_0 =1 ,s_0 =2
  5. 对于1 \le m \le r,按如下递推式计算g_ms_m
    g_m \equiv s_{m-1}(g_{m-1}-g_{m-1}^2-n) \pmod{3^{2^m}}
    s_m \equiv 2s_{m-1}-2g_{m-1}{s_{m-1}}^2 \pmod{3^{2^m}}
  6. 计算 g \equiv g_{r-1}-s_{r-1}(g_{r-1}^2-n) \pmod{3^l}
  7. 如果g^2 =n
    输出True
  8. 如果(3^l-g)^2 =n
    输出True
  9. 输出False


判定n(奇数)是否为d(奇数)次方数:N_d(n)

  1. 计算 l =\left \lceil \frac{1}{d} \log(n) \right \rceil
  2. 计算 r =\left \lfloor \ \log(l) \right \rfloor
  3. g_0 =1 ,s_0 =1
  4. 对于1 \le m \le r,按如下递推式计算g_ms_m
    g_m \equiv s_{m-1}(g_{m-1}-g_{m-1}^d-n) \pmod{2^{2^m}}
    s_m \equiv 2s_{m-1}-(d-1)g_{m-1}^{d-1}{s_{m-1}}^2 \pmod{2^{2^m}}
  5. 计算 g \equiv g_{r-1}-s_{r-1}(g_{r-1}^d-n) \pmod{2^l}
  6. 如果g^d =n
    输出True
  7. 输出False


判定n是否为素数:IsPrime(n)

  1. 如果n \equiv 0 \pmod{2}
    输出False
  2. 如果n \equiv 0 \pmod{3}
    输出False
  3. 对于3 \le d \le \left \lceil \frac{1}{2} \log(n) \right \rceil,以步长为2(即对所有奇数d)计算N_d(n)
    如果N_d(n) =True
    输出False
  4. 计算 r =\left \lceil \ \log(n)^2 \right \rceil
  5. 对于1 \le t \le \ \log(n)^2,计算n^t\,\bmod\,r
    如果n^t \equiv 1 \pmod{r}
    r =r+1, t =1,重新检测(回到5.)
  6. 对于3 \le a \le r,计算GCD(a,n)
    如果1 <GCD(a,n) <n
    输出False
  7. 如果n <r
    输出True
  8. h =0
  9. 对于1 \le q <r,计算GCD(q,r)
    如果GCD(q,r) =1
    h =h+1
  10. 对于1 \le c \le \left \lfloor \ \sqrt{h} \log(n) \right \rfloor,计算(X+c)^n\,\bmod\,X^r-1,n
    如果(X+c)^n \not\equiv X^n+c \pmod{X^r-1,n}
    输出False
  11. 输出True

相關頁面[编辑]

  1. ^ 1.0 1.1 1.2 Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
  2. ^ H. W. Lenstra, Jr. and Carl Pomerance, "Primality Testing with Gaussian Periods", preliminary version July 20, 2005.

外部連接[编辑]

参考资料[编辑]