大數素性檢測

資訊安全數學基礎讀書報告，列舉了常見确定性檢測算法和機率性檢測算法，并加入了自己的看法和讨論。

大數的素性檢測可以分為确定性的素性檢測和機率性的素性檢測

确定性的素性檢測在小整數的素性檢測中雖然已經夠用，但是在大整數的素性檢測中，這些算法明顯複雜度大大增加，是以人們又尋找到了更加高效的機率性素性檢測來尋找大素數。

這裡僅僅舉出比較常見或者比較著名的素性檢測方法。

\[\forall n\in N^{+},如果對所有i\le\sqrt{n},i\in N^{+},滿足i\not\mid n，則n為素數。。

\]

想法

對于這個素性檢測的一種優化是i可以換作小于n的平方根的素數，因為小于n的平方根的數都有素因子，是以可以優化，但是這種優化僅僅對于小整數而言好用。

這裡的時間複雜度仍然是指數級的，但是我們期望能夠有多項式級的算法，幫助我們高效進行素性檢測。

時間複雜度

\[O(2^{(logN)/2})

\[梅森數是形如2^{n}-1的數，記為M_n;若其為素數，則稱之為梅森素數。

并且當n為合數時，梅森數也為合數；當n為素數是，梅森數不一定都是素數

\[\begin{align*}

&1.定義序列 S_{i},i>0\\

&2.S_i=4,i=0;\\

&3.S_i=S_{i-1}^2-2,i>0\\

&4.那麼M_n為素數當且僅當S_{n-2} \equiv0(modM_n)\\

&5.否則M_p為合數\\

&6.時間複雜度O(n^{3})

\end{align*}

這裡的确定性算法雖然時間複雜度很低，但是僅僅适用于梅森數的檢驗，十分具有局限性，但是對于大素數的尋找很有幫助，最近幾個最大素數便是該算法尋找到的。

在這個結論的證明中，因為這是個序列，是以自然而然想到用數學歸納法，但是其中構造的方法頗為巧妙，構造一對

\[{\displaystyle \omega {\bar {\omega }}=(2+{\sqrt {3}})(2-{\sqrt {3}})=1}

用于證明每個Si都滿足

\[{\displaystyle s_{i}=\omega ^{2^{i}}+{\bar {\omega }}^{2^{i}}}

證明充分性時，運用了反證法，再引入群的概念，通過群元素的階和素因子的性質導出沖突。

證明必要性時，運用了二次剩餘，歐拉準則，費馬小定理以及初等群論等來證明。

同樣的，也有同類型的素性檢測，Pepin測試，但是它也僅适用于費馬數，這樣的局限性過于緻命。

這是最為著名的确定性素性測試，因為它的出世成功使素數判定的時間複雜度降到了多項式複雜度，并且沒有依賴任何未得到證明的猜想。

該證明涉及費馬小定理，群、環和域等知識，中間具體内容本人難以了解。

AKS素性測試主要是基于以下定理

\[(x+a)^n\equiv(x^n+a)(mod x^{r-1},n)

具體計算中可以使用貝祖定理進行公約數的計算。

算法操作：

&1.輸入：整數 n > 1\\

&2.若存在整數a > 0 且b > 1 ，令 n = ab ；則輸出合數\\

&3.找出最小的 r 令 ordr(n) > log2(n).\\

&4.若對某些a ≤ r，1 < gcd(a,n) < n，輸出合數。(gcd是指最大公約數)。\\

&5.若 n ≤ r, 輸出素數。\\

&6.對 a = 1 到 {\displaystyle \scriptstyle \lfloor \scriptstyle {\sqrt {\varphi (r)}}\log(n)\scriptstyle \rfloor }\scriptstyle \lfloor \scriptstyle {\sqrt {\varphi (r)}}\log(n)\scriptstyle \rfloor 的所有數，

如果 (X+a)n≠ Xn+a (mod Xr − 1,n), 輸出合數。\\

&7.輸出素數。

這個素性檢驗是根據費馬小定理的逆定理來篩選大素數的。

\[如果p是素數，{\displaystyle 1\leq a\leq p-1}，那麼a^{{p-1}}\equiv 1{\pmod {p}}

但是由于其逆定理并不正确，對于卡邁克爾數即滿足費馬小定理的逆定理但是不為素數的數，雖然卡邁克爾數很少，在1~100000000範圍内的整數中，隻有255個卡邁克爾數，但是已經使他的效果落後于Miller-Rabin和Solovay-Strassen素性檢驗。

&1.輸入：n\ge3；k：參數之一來決定檢驗需要進行的次數。\\

&2.輸出：當n是合數時，否則可能是素數：\\

&3.重複k次：\\

&在[2, n − 2]範圍内随機選取a\\

&如果a^{n − 1} mod n ≠ 1那麼傳回合數\\

&傳回可能是素數

出錯的機率

在選取底數a時，有二分之一的機率出錯，但是可以通過多次選取底數來使出錯機率降下期望值。

\[在重複k次成立的情況下，n為合數的可能性小于\frac{1}{2^k}

突破

2016年，我國物流勞工提出了卡邁克爾數判别準則，

&n=(6k+1)(18k+1)(54k^2+12k+1)=5832^4+2592k^3+450k^2+36k+1\\

&(n-1)/(6k)=972k^3+432k^2+75k+6\\

&(n-1)/(18k)=324k^3+144k^2+25k+2\\

&(n-1)/(54k^2+12k)=108k^2+24k+3

如果6k+1,18k+1,54k^2+12k+1都是素數(比如k=1，2)，那麼n必然是卡邁克爾數,與先前的判别法相比，這個公式的亮點就是新發現的二次式也可以作為卡邁克爾數因子。

\[O(k×log3n)

在模平方剩餘判别時，歐拉判别法則要求模為奇素數，但是雅克比符号弱化了這樣的條件，隻要求模為奇整數，這樣的變化可以用于判斷模平方剩餘，但是和歐拉定理不能等價，于是會存在僞素數。

歐拉僞素數:

設n為正奇合數，設整數b與n互素。如果整數n和b滿足條件

\[b^{\frac{n-1}{2}}\equiv(\frac{b}{n})(modn)

則n叫做對于基b的歐拉-雅克比僞素數。

Solovay-Stassen算法：

&1.輸入：n，一個值以測試素性

k，其确定測試的準确性的參數\\

&2.輸出：n是合數，否則可能是素數\\

&3.重複k次：在 [2, n − 1]\\

&範圍内随機選擇一個{\displaystyle x\gets \left({\tfrac {a}{n}}\right)} \\

&如果 x = 0 或 {\displaystyle a^{(n-1)/2}\not \equiv x{\pmod {n}}} \\

&然後傳回合數\\

&否則傳回可能是素數

所有歐拉-雅克比僞素數同時是費馬僞素數，這個判别公式對所有素數都成立，因而可以用于機率素性檢驗，他的可靠性是費馬素性檢驗的兩倍多。

\[O(k·log3 n)

素性檢測首先利用了因數分解式，将幂次n-1降低為以2為階的各次幂，再利用中國剩餘定理，推出強僞素數的滿足條件，在算法優化中，采用模平方算法降低複雜度，這也是該算法的優勢之一，大大提高了效率。

&給定奇整數n\ge3和安全參數k\\

&寫n-1=2^st,其中t為奇整數\\

&1.随機選取整數b，2\le b \le n-2\\

&2.計算r_0\equiv b^t(modn)\\

&3.\\&（1）如果r_0=1或r_0=n-1,則通過檢驗，回到第一步，重選b\\

&（2）否則有r_0\neq1以及r_0\neq n-1,計算r_1\equiv r_0^2(modn)\\

&以此類推,直到n-2為止，通過檢驗則輸出可能為素數，否則為合數

\[在k次檢測通過的情況下，n為合數的機率小于\frac{1}{4^k}

相比之下，這樣的出錯機率遙遙領先與費馬素性檢測和Solovay-Stassen素性檢測。

模平方算法下

\[{\displaystyle O(k\log ^{3}n)}

轉載請注明出處：https://www.cnblogs.com/merk11/

大數素性檢測的發展，從最初的基于單一定理進行窮舉檢測，到特殊素數的檢測，再到一般素數的綜合檢測，一步一步從複雜到簡單，從特殊到一般；不僅如此，由于素數的重要性，人們更追求在更短時間内判定出素數，通過弱化某些條件或者尋找某些定理逆命題的可靠性，來機率性地判别素數，在機率性素數檢測發展中，Miller-Rabin最為著名，也是由于他能夠采用更加優良的模平方算法，大大降低了算法複雜度，使大數素數的判定速率有了質的飛躍。

數學家們至今仍然在素性檢測的山峰上攀登，在學習過程中，我尋找到了不少基于黎曼猜想的素性檢測，由于黎曼猜想并未完全被證明，這些素性檢測便仍然有很大的局限性。

各個素性檢測各有優勢，對待不同的檢測要求，大數範圍，選取的素性檢測也不同。素性檢測在對應的場景，經過人工的調試，能夠發揮更大的作用，比如機率性檢測的安全參數k便可以根據要求而改變。