素性測試

素數又稱質數,是在大於1的整數中,只能被1和其自身整除的數(如2、3、5等)。素性測試是檢驗一個給定的整數是否為素數的測試。

基本介紹

  • 中文名:素性測試
  • 檢驗:一個給定的整數是否為質數的測試
  • 嘗試:從2到√N的整數是否整除N
  • 利用費馬小定理來測試
確定型算法,隨機算法,

確定型算法

上下素性判定法
首先,本文英文字母都表示整數,上半部B 》3N 》W,下半部B 》W 》3N。大於3的素數只有6N-1和6N+1兩種形式,我們只需判定這兩種數是素數還是合數即可。
命題 1 對於B=36N+1 形數而言。
若不定方程(3N)^2+N-(B-1)/36=W^2 有整數解,
則 6(3N-W)+1 是小因子數;6(3N+W)+1 是大因子數。
若不定方程 (3N)^2-N-(B-1)/36=W^2 有整數解,
則 6(3N-W)-1 是小因子數;6(3N+W)-1 是大因子數。
兩式都無解,是素數。
命題 2對於B=36N+7 形數而言。
若不定方 (3N)^2+4N-(B-7)/36=W^2+W 有整數解,
則 6(3N-W)+1 是小因子數,6(3N+W+1)+1 是大因子數。
若不定方程 (3N+2)^2+2N+2-(B+29)/36=W^2+W 有整數解,
則 6(3N+2-W)-1 是小因子數,6(3N+W+3)-1 是大因子數。
兩式都無解,是素數。
命題 3對於B=36N+13 形數而言。
若不定方程 (3N+1)^2+N-(B-13)/36=W^2 有整數解,
則 6(3N+1-W)+1 是小因子數,6(3N+1+W)+1是大因子數。
若不定方程 (3N+2)^2-N-(B+23)/36=W2 有整數解,
則 6(3N+2-W)-1 是小因子數,6(3N+2+W)-1是大因子數。
兩式都無解,是素數。
命題 4 對於B=36N+19 形數而言。
若不定方程(3N+1)^2+4N+1-(B-19)/36=W^2 +W 有整數解,
則 6(3N+1-W)+1 是小因子數;6(3N+2+W)+1 是大因子數。
若不定方程 (3N+1)^2+2N+1-(B+17)/36=W^2 +W 有整數解,
則 6(3N+1-W)-1 是小因子數;6(3N+2+W)-1 是大因子數。
兩式都無解,是素數。
命題 5 對於B=36N+25 形數而言。
若不定方 (3N+2)^2+N-(B-25)/36=W^2有整數解,
則 6(3N+2-W)+1 是小因子數,6(3N+2+W)+1 是大因子數。
若不定方程 (3N+1)^2-N-(B+11)/36=W^2有整數解,
則 6(3N+1-W)-1 是小因子數,6(3N+1+W)-1 是大因子數。
兩式都無解,是素數。
命題 6 對於B=36N+31 形數而言。
若不定方程 (3N+2)^2+4N+2-(B-31)/36=W^2 +W 有整數解,
則 6(3N+2-W)+1 是小因子數,6(3N+3+W)+1是大因子數。
若不定方程 (3N+1)^2-4N-1-(B+5)/36=W^2+W有整數解,
則 6(3N-W)-1 是小因子數,6(3N+1+W)-1是大因子數。
兩式都無解,是素數。
命題 7對於B=36N-1 形數而言。
若不定方程(3N)^2-N+(B-1)/36=W^2 有整數解,
則 6(3N-W)+1 是小因子數;6(3N+W)-1 是大因子數。
若不定方程 (3N)^2+N+(B-1)/36=W^2 有整數解,
則 6(W-3N)-1 是小因子數;6(W+3N)+1 是大因子數。
兩式都無解,是素數。
命題 8對於B=36N+5 形數而言。
若不定方 (3N)^2+2N+(B-5)/36=W^2+W 有整數解,
則 6(W-3N)+1 是小因子數,6(W+3N+1)-1 是大因子數。
若不定方程 (3N+2)^2+4N+2+(B+31)/36=W^2+W 有整數解,
則 6(W-3N-2)-1 是小因子數,6(W+3N+3)+1 是大因子數。
兩式都無解,是素數。
命題 9對於B=36N+11 形數而言。
若不定方程 (3N+1)^2-N+(B-11)/36=W^2 有整數解,
則 6(W-3N-1)+1 是小因子數,6(W+3N+1)-1是大因子數。
若不定方程 (3N+2)^2+N+(B+25)/36=W2 有整數解,
則 6(W-3N-2)-1 是小因子數,6(W+3N+2)+1是大因子數。
兩式都無解,是素數。
命題 10 對於B=36N+17 形數而言。
若不定方程(3N+1)^2+2N+1+(B-17)/36=W^2 +W 有整數解,
則 6(W-3N-1)+1 是小因子數;6(W+3N+2)-1 是大因子數。
若不定方程 (3N+1)^2+4N+1+(B+19)/36=W^2 +W 有整數解,
則 6(W-3N-1)-1 是小因子數;6(W+3N+2)+1 是大因子數。
兩式都無解,是素數。
命題 11 對於B=36N+23 形數而言。
若不定方 (3N+2)^2-N+(B-23)/36=W^2有整數解,
則 6(W-3N-2)+1 是小因子數,6(W+3N+2)+1 是大因子數。
若不定方程 (3N+1)^2+N+(B+13)/36=W^2有整數解,
則 6(W-3N-1)-1 是小因子數,6(W+3N+1)+1 是大因子數。
兩式都無解,是素數。
命題 12 對於B=36N+31 形數而言。
若不定方程 (3N+2)^2+2N+2+(B-29)/36=W^2 +W 有整數解,
則 6(W-3N-2)+1 是小因子數,6(W+3N+3)-1是大因子數。
若不定方程 (3N)^2-4N+(B+7)/36=W^2+W有整數解,
則 6(W-3N)-1 是小因子數,6(W+3N+1)+1是大因子數。
兩式都無解,是素數。
試除法 嘗試從2到√N的整數是否整除N。 AKS 質數測試 PRIMES in P 這篇論文提到的方法,是第一個多項式時間的質數測試算法。

隨機算法

費馬測試 利用費馬小定理來測試。 Miller-Rabin 質數測試 歐拉-雅科比測試 對於N,挑選任意的M,測試(M/N)≡M^[(N-1)/2]。如果不成立,則N為合數。否則N有一半的機率是質數。

熱門詞條

聯絡我們