質數測試 - 維基百科，自由的百科全書

質數測試或質數判定，是檢驗一個給定的整數是否為質數的測試。

質數

質數是除了自身和1以外，沒有其它質數因子的自然數。自從歐幾里得證明了有無窮個質數以後，人們就企圖尋找一個可以構造所有質數的公式，尋找判定一個自然數是不是質數的方法。因為質數的地位非常重要。

質數判定的歷史

鑑別一個自然數是質數還是合數，這個問題在中世紀就引起人們注意，當時人們試圖尋找質數公式，到了高斯時代，基本上確認了簡單的質數公式是不存在的，因此，高斯認為對質性判定是一個相當困難的問題。從此以後，這個問題吸引了大批數學家。質性判斷演算法可分為兩大類，確定性演算法及隨機演算法。前者可給出確定的結果但通常較慢，後者則反之。詳見以下列表。

確定型演算法

試除法（愛拉托散尼篩法）
- 嘗試從 $2$ 到 ${\sqrt {N}}$ 的整數是否整除 $N$ 。

// 以 C 語言實現埃拉托斯特尼篩法
// 用以判斷質數的 is_prime 副函式
int is_prime(int x)
{
    if(x < 2) return 0;            // 1 不是質數，且不考慮負整數與 0，故輸入 x<=1 時回傳 0
    for(int i = 2; i * i <= x; ++i)
        if(x % i == 0) return 0;    // 一旦出現整除，回傳 0
    return 1;                       // 迴圈跑完後都沒有整除，回傳 1
}

威爾遜定理
- 當且僅當 $p$ 為質數時：

(p-1)!\ \equiv \ -1\ ({\mbox{mod}}\ p)

盧卡斯-萊默檢驗法
AKS質數測試
- PRIMES is in P這篇論文提到的方法，是第一個多項式時間的質數測試演算法。

隨機演算法

費馬質性檢驗
- 利用費馬小定理來測試。
米勒-拉賓檢驗
歐拉-雅科比測試
- 對於n，挑選隨機的 $a<n$ ，測試 $({a \over n})=a^{(n-1)/2}\mod n$ ，這裏 $({a \over n})$ 為雅可比符號。如果N為質數，等式一定成立；如果N為合數，等式有一半的概率不成立。

參見

外部連結

閱論編質數類

公式	卡羅爾質數（ $（2 n －1） 2 －2$ ）費馬質數（ $2 2 n ＋1$ ）梅森質數（ $2 p －1$ ）雙重梅森質數（ $2 2 p －1 －1$ ）瓦格斯塔夫質數 $（2 p ＋1）／3$ 普羅斯質數（ $k \cdot2 n ＋1$ ）階乘質數（ $n ！\pm1$ ）質數階乘質數（ $p n ＃\pm1$ ）歐幾里得數（ $p n ＃＋1$ ）畢達哥拉斯質數（ $4 n ＋1$ ）皮爾龐特質數（ $2 m \cdot3 n ＋1$ ） Quartan質數（ $x 4 ＋ y 4$ ）（英語：Quartan prime）索利納斯質數（ $2 m \pm2 n \pm1$ ）（英語：Solinas prime）卡倫質數（ $n \cdot2 n ＋1$ ）胡道爾質數（ $n \cdot2 n －1$ ）立方質數（ $x 3 － y 3 ）／（ x － y$ ）萊蘭質數（ $x y ＋ y x$ ）塔別脫質數（ $3\cdot2 n －1$ ）威廉士質數（ $（ b -1）\cdot b n －1$ ）（英語：Williams number）米爾斯質數（［ $A 3 n$ ］） Kynea質數（ $（2 n ＋1） 2 －2$ ）

整數數列	斐波納契質數盧卡斯質數佩爾質數 NSW質數佩蘭偽質數

屬性	維費里希質數質數對（英語：Wieferich pair）沃爾-孫-孫質數沃爾斯滕霍爾姆質數（英語：Wolstenholme prime）韋爾遜質數幸運質數 Fortunate質數（英語：Fortunate number）拉馬努金質數皮萊質數正則質數強質數斯特恩質數超奇異質數（橢圓曲線）（英語：Supersingular prime (algebraic number theory)）超奇異質數（月光理論）好質數超質數希格斯質數高互補歐拉商數唯一質數

基數相關	回文質數反質數循環單位質數 $（10 n －1）／9$ 可交換質數環狀質數可截短質數極小質數精緻質數（英語：Delicate prime）原始質數全循環質數唯一質數快樂質數自我質數 Smarandache–Wellin質數 Strobogrammatic質數（英語：Strobogrammatic prime）二面質數四面質數（英語：Tetradic number）

圖形	孿生質數（ $p ， p ＋2$ ）孿生倍鏈（ $n \pm 1，2 n \pm 1，4 n \pm 1，\dots$ ）（英語：Bi-twin chain）三胞胎質數（ $p ， p ＋2 或 p ＋4， p ＋6$ ）四胞胎質數（ $p ， p ＋2， p ＋6， p ＋8$ ）質數k元組（英語：Prime k-tuple）表兄弟質數（ $p ， p ＋4$ ）六質數（ $p ， p ＋6$ ）陳質數索菲·熱爾曼／安全質數（ $p ，2 p ＋1$ ）坎寧安鏈（ $p ，2 p \pm 1，4 p \pm 3，8 p \pm 7，...$ ）（英語：Cunningham chain）等差數列（ $p ＋ a\cdotn ， n ＝0，1，2，3，...$ ）（英語：Primes in arithmetic progression）平衡質數（ $連續的 p － n ， p ， p ＋ n$ ）

數量級	超大質數（1,000,000+以上）（英語：Megaprime）已知最大質數列表（英語：List of largest known primes and probable primes）

複數	艾森斯坦質數高斯質數

合數	偽質數卡塔蘭（英語：Catalan pseudoprime）橢圓（英語：Elliptic pseudoprime）歐拉歐拉-雅可比費馬弗羅貝尼烏斯（英語：Frobenius pseudoprime）盧卡斯（英語：Lucas pseudoprime）佩蘭索默爾–盧卡斯（英語：Somer–Lucas pseudoprime）強卡邁克爾數殆質數半質數楔形數 Interprime 有害數（英語：Pernicious number）

相關	擬質數（英語：Probable prime）產業等級質數非法質數質數公式質數間隙 $X 2 ＋1$ 質數質數定理質數計算函數質數測試

前60個質數	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281

質數列表

閱論編數論算法

質數測試	AKS APR（英語：Adleman–Pomerance–Rumely primality test） Baillie–PSW（英語：Baillie–PSW primality test）橢圓曲線（英語：Elliptic curve primality） Pocklington（英語：Pocklington primality test）費馬盧卡斯（英語：Lucas primality test）盧卡斯-萊默 Lucas–Lehmer–Riesel（英語：Lucas–Lehmer–Riesel test）普羅斯 Pépin（英語：Pépin's test）二次Frobenius（英語：Quadratic Frobenius test） Solovay–Strassen（英語：Solovay–Strassen primality test）米勒-拉賓

質數生成（英語：Generating primes）	阿特金篩法（英語：Sieve of Atkin）愛拉托散尼篩法 Pritchard篩法（英語：Sieve of Pritchard） Sundaram篩法（英語：Sieve of Sundaram）輪式因數分解法（英語：Wheel factorization）

整數分解	連分數分解 (CFRAC)（英語：Continued fraction factorization） Dixon's（英語：Dixon's factorization method） Lenstra橢圓曲線 (ECM)（英語：Lenstra elliptic-curve factorization）歐拉因式分解法波拉德ρ算法（英語：Pollard's rho algorithm） p − 1（英語：Pollard's p − 1 algorithm） p + 1（英語：Williams's p + 1 algorithm）二次篩選法普通數體篩選法特殊數體篩選法 (SNFS)（英語：Special number field sieve）有理篩選法費馬因式分解法（英語：Fermat's factorization method） Shanks二次形式（英語：Shanks's square forms factorization）試除法秀爾演算法

乘法算法	古埃及乘算（英語：Ancient Egyptian multiplication）長乘法卡拉楚巴算法圖姆-庫克算法頌哈吉-施特拉森演算法富爾算法（英語：Fürer's algorithm）

歐幾里德除法除法算法	二進制（英語：Binary division）倍塊法（英語：Chunking (division)） Fourier（英語：Fourier division） Goldschmidt（英語：Goldschmidt division） Newton-Raphson（英語：Newton–Raphson division）長除法短除法 SRT

離散對數	大步小步算法波拉德ρ算法 Pollard kangaroo（英語：Pollard's kangaroo algorithm） Pohlig–Hellman（英語：Pohlig–Hellman algorithm） Index calculus（英語：Index calculus algorithm） Function field sieve（英語：Function field sieve）

最大公因數	二進制最大公因數算法（英語：Binary GCD algorithm）輾轉相除法擴展歐幾里得算法 Lehmer's（英語：Lehmer's GCD algorithm）

二次剩餘	Cipolla（英語：Cipolla's algorithm） Pocklington's（英語：Pocklington's algorithm） Tonelli–Shanks（英語：Tonelli–Shanks algorithm） Berlekamp（英語：Berlekamp–Rabin algorithm） Kunerth（英語：Kunerth's algorithm）

其他算法	Chakravala（英語：Chakravala method） Cornacchia（英語：Cornacchia's algorithm）整數關係（英語：Integer relation algorithm）（LLL（英語：Lenstra–Lenstra–Lovász lattice basis reduction algorithm）；KZ（英語：Korkine–Zolotarev lattice basis reduction algorithm））平方求冪整數平方根模冪運算蒙哥馬利算法 Schoof（英語：Schoof's algorithm）特拉亨伯格系統（英語：Trachtenberg system）

斜體表示該算法只適用於特殊形式的數字