1、精選優(yōu)質(zhì)文檔-傾情為你奉上第六章 素性檢驗 6.1 擬素數(shù)引例：根據(jù)Fermat小定理，我們知道：如果n是一個素數(shù)，則對任意整數(shù)b,(b,n)=1,有 由此，我們得到：如果一個整數(shù)b,(b,n)=1,使得 ，則n是一個合數(shù)。定義1：設(shè)n是一個奇合數(shù)，如果整數(shù)b,(b,n)=1使得同余式 成立，則n叫做對于基b的擬素數(shù)。引理：設(shè)d,n都是正整數(shù)，如果d能整除n則能整除定理1：存在無窮多個對于基2的擬素數(shù)。定理2：設(shè)n是一個奇合數(shù)，則(i)n是對于基b,(b,n)=1),的擬素數(shù)當(dāng)且僅當(dāng)b模n的指數(shù)整除n-1。(ii)如果n是對于基(,n)=1),和基，(,n)=1),的擬素數(shù)，則n是對于基的擬素

2、數(shù)。(iii)如果n是對于基b,(b,n)=1),的擬素數(shù)，則n是對于基的擬素數(shù)。(iv)如果有一個整數(shù)b，(b,n)=1),使得同余式不成立，則模n的簡化剩余系中至少有一半的數(shù)使得該同余式不成立。/Fermat 素性檢驗給定奇整數(shù)和安全參數(shù)。1. 隨即選取整數(shù),；2. 計算;3. 如果，則n是合數(shù)；4. 上述過程重復(fù)次；定義2：合數(shù)n稱為Carmichael數(shù)，如果對所有的正整數(shù)b，(b,n)=1, 都有同余式成立定理3：設(shè)n是一個奇合數(shù)。(i)如果n被一個大于1平方數(shù)整除，則n不是Carmichael數(shù)。(ii)如果是一個無平方數(shù)，則n是Carmichael數(shù)的充要條件是 ，定理4：每個C

3、armichael數(shù)是至少三個不同素數(shù)的乘積注：1.存在無窮多個Carmichael數(shù)2.當(dāng)n充分大時，區(qū)間內(nèi)的Carmichael數(shù)的個數(shù)大于等于 6.2 Euler擬素數(shù)引例：設(shè)n是奇素數(shù)，根據(jù)定理，我們有同余式 對任意整數(shù)b成立 因此，如果存在整數(shù)b，(b,n)=1,使得 則n不是一個素數(shù)。定義1:設(shè)n是一個正奇合數(shù)，設(shè)整數(shù)b與n互素，如果整數(shù)n和b滿足條件： 則n叫做對于基b的Euler擬素數(shù)。定理1：如果n是對于基b的Euler 擬素數(shù)，則n是對于基b的擬素 數(shù)。 /Solovay-Stassen素性檢驗給定奇整數(shù)和安全參數(shù).1. 隨即選取整數(shù)，；2. 計算3. 如果以及，則n是合數(shù)

4、；4. 計算Jacobi符號5. 如果，則你是合數(shù)；6. 上述過程重復(fù)次。 6.3 強擬素數(shù)引例：設(shè)n是正奇整數(shù)，并且有，則我們有如下因數(shù)分解式： 因此，如果有同余式 則如下同余式至少有一個成立： 定義1：設(shè)n是一個奇合數(shù)，且有表達式，其中t為奇數(shù)，設(shè)整數(shù)b與n互素，如果整數(shù)n和b滿足條件： 或者存在一個整數(shù)，使得 則n叫做對于基b的強擬素數(shù)。定理1：存在無窮多個對于基2的強擬素數(shù)。定理2:如果n是對于基b的強擬素數(shù)，n是對于基b的Euler擬素數(shù)。定理3：設(shè)n是一個奇合數(shù)，則n是對于基b，的強擬素數(shù)的可能性至多為25%。/Miller-Rabin素性檢驗給定奇整數(shù)和安全參數(shù)k。寫，其中t為奇整數(shù)。1. 隨機選取整數(shù)。2. 計算；3. (i)如果或，則通過檢驗，可能為素數(shù)。回到1，繼續(xù)選取另一個隨機整數(shù); (ii)否則，有以及，我們計算；4. (i)如果，則通過檢驗，可能為素數(shù)。回到1，繼續(xù)選取另一個隨機整數(shù)； (ii)否則，有，我們計算； 如