素數測試演算法

⑴ 素性測試的隨機演算法

費馬測試 利用費馬小定理來測試。 Miller-Rabin 質數測試 歐拉-雅科比測試 對於N，挑選任意的M，測試（M/N）≡M^[(N-1)/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是大因子數。兩式都無解，是素數。

⑵ 判斷一個數是否為素數的演算法

找質數的方法：寫出這個數的因數。再判斷這個數是質數還是合數。
1、一個數除了1和本身，不再有別的約數，這樣的數叫做質數或者素數。例如：2，3，5，7，11，13，17，19，23，29等等。
2、一個數，除了1和本身，還的別的因數，這樣的數叫做合數。例如4、8、8、9等等。例如：2的所有因數是1和2兩個，所以2是質數。例如6的所有因數是：1，2，3，6。一共是4個，所以6是合數。

找因12的因數：
1×12=12 2×6=12 3×4=12 所以12的因數有：1，2，3，4，6，12。共6個。
找因數的方法可以把這個數分成兩個因數相乘的積。從一開始比較容易找，寫的時候最好能從小到大寫出來。重復的只能寫一個。例如9的因數：1×9=9 3×3=9 9的因數是：1，3，9共3個。（重復的3隻能寫一個。）

⑶ 我們知道整數13是素數,求解13是素數的演算法有多種方法,第一種方法用窮舉法測試

素數定義：只能被1和自身整除的自然數。

13/1=13

13/2=6.5

13/3=

13/4=

13/5=

13/12=

13/13=1

發現除了1和13 能夠整除，其他不行。因此是13是素數。

凡是除數是偶數的可以不用試驗。因為 素數必須是奇數。奇數除偶數不是自然數。

這樣就可以只試驗 3，5，7，9，11，能否整除13

(3)素數測試演算法擴展閱讀

整數a除以整數b （ b≠0 ） ，除得的商正好是整數而沒有餘數我們就說a能被b整除（也可以說b能整除a ）除盡的意義甲數除以乙數，所得的商是整數或有限小數而余數也為0時，我們就說甲數能被乙數除盡， （或者說乙數能除盡甲數）這里的甲數、乙數可以是自然數，也可以是小數（乙數不能為0）。

1、能被2整除的數的特徵：個位上是0、2、4、6、8。

2、能被5整除的數的特徵：個位上是0或5。

3、能被3整除的數的特徵： 一個數的各個數位上的數之和能被3整除，這個數就能被3整除。

⑷ Miller Rabin演算法的簡介

Miller-Rabin演算法是目前主流的基於概率的素數測試演算法，在構建密碼安全體系中佔有重要的地位。通過比較各種素數測試演算法和對Miller-Rabin演算法進行的仔細研究，證明在計算機中構建密碼安全體系時， Miller-Rain演算法是完成素數測試的最佳選擇。通過對Miller-Rabin 算 法底層運算的優化，可以取得較以往實現更好的性能。隨著信息技術的發展、網路的普及和電子商務的開展， 信息安全逐步顯示出了其重要性。信息的泄密、偽造、篡改 等問題會給信息的合法擁有者帶來重大的損失。在計算機中構建密碼安全體系可以提供4種最基本的保護信息安全的服 務：保密性、數據完整性、鑒別、抗抵賴性，從而可以很大 程度上保護用戶的數據安全。在密碼安全體系中，公開密鑰 演算法在密鑰交換、密鑰管理、身份認證等問題的處理上極其有效，因此在整個體系中佔有重要的地位。目前的公開密鑰 演算法大部分基於大整數分解、有限域上的離散對數問題和橢 圓曲線上的離散對數問題，這些數學難題的構建大部分都需 要生成一種超大的素數，尤其在經典的RSA演算法中，生成的素數的質量對系統的安全性有很大的影響。目前大素數的生 成，尤其是隨機大素數的生成主要是使用素數測試演算法，本 文主要針對目前主流的Miller-Rabin 演算法進行全面系統的分析 和研究，並對其實現進行了優化。

⑸ 判斷100位的整數為素數的演算法

與1到根號這個數+1相除，都不能整除就為素數

⑹ 判斷一個數是否是素數的最簡便演算法

追求效率的話
最高的是 miller_rabin
演算法
最好有一定的數論知識再去看
另一個簡單方法是
可以o(n)
求出素數
然後再判斷就行了
多個素數判斷時效率較高

⑺ 求判斷一個數是否為素數的最簡單演算法

追求效率的話 最高的是 Miller_Rabin 演算法 最好有一定的數論知識再去看
另一個簡單方法是 可以O(n) 求出素數 然後再判斷就行了 多個素數判斷時效率較高

⑻ 判斷一個正整數是否是素數的常用演算法是 A，排序法 B，回溯法 C，遞歸法 D，窮舉法

摘要 您好，判斷一個正整數是否是素數的常用演算法是D窮舉法

⑼ c語言求素數的演算法

根據素數的性質，代碼設計如下：

設計一：判斷n是否能被1~n-1整除，不能整除為素數

#include<stdio.h>

int main()

{

int i, n;

scanf("%d", &n);

for (i = 2; i < n ; i++)

{

if (n%i == 0)

break;

}

if (i < n) printf("This is not a prime.");

else printf("This is a prime.");

return 0;

}

設計二：判斷n是否能被2~√n間的整數整除，不能整除為素數

#include<stdio.h>

#include<math.h>

int main()

{

int n,i;

double k;

scanf("%d", &n);

k = sqrt(n);

for (i = 2; i <= k;i++)

{

if (n%i == 0) break;

}

if (i <=k) printf("This is not a prime.");

else printf("This is a prime");

return 0;

}

(9)素數測試演算法擴展閱讀：

1.素數的定義是只能被1和他本身整除,1不是素數.因此要判斷一個數是否為素數.就要判斷它能不能被比他小的所有素數整除,這是一個演算法.(寫到演算法時,我只能寫出用它除以比他小的所有數,造成運算速度低下)

2.如果一個質數大於根號n，而n可以除盡它，那麼n必然也可以除盡一個更小的質數。由此可以得到一個法2較快的素數判斷演算法