信息安全數(shù)學(xué)基礎(chǔ)知識點

1、信 息 安 全 數(shù) 學(xué) 基 礎(chǔ) 知識 點精品好資料 -如有侵權(quán)請聯(lián)系網(wǎng)站刪除精品好資料 -如有侵權(quán)請聯(lián)系網(wǎng)站刪除第六章 素性檢驗 6.1 擬素數(shù)引例：根據(jù) fermat小定理，我們知道：如果n 是一個素數(shù)，則對任意整數(shù) b,(b,n)=1,有)(mod11nbn由此，我們得到：如果一個整數(shù)b,(b,n)=1,使得)(mod11nbn，則 n是一個合數(shù)。定義 1：設(shè) n是一個奇合數(shù)，如果整數(shù)b,(b,n)=1使得同余式)(mod11nbn成立，則 n 叫做對于基 b 的擬素數(shù)。引理：設(shè) d,n都是正整數(shù)，如果d能整除 n則12d能整除12n定理 1：存在無窮多個對于基2的擬素數(shù)。定理 2：設(shè) n

2、是一個奇合數(shù)，則(i)n 是對于基 b,(b,n)=1),的擬素數(shù)當且僅當b 模 n 的指數(shù)整除 n-1。(ii)如果 n是對于基1b(1b,n)=1),和基2b，(2b,n)=1),的擬素數(shù)，則n是對于基21bb的擬素數(shù)。(iii) 如果 n 是對于基 b,(b,n)=1),的擬素數(shù)，則 n 是對于基1b的擬素數(shù)。(iv)如果有一個整數(shù) b，(b,n)=1),使得同余式)(mod11nbn不成立，則模 n 的簡化剩余系中至少有一半的數(shù)使得該同余式不成立。精品好資料 -如有侵權(quán)請聯(lián)系網(wǎng)站刪除精品好資料 -如有侵權(quán)請聯(lián)系網(wǎng)站刪除/ fermat 素性檢驗給定奇整數(shù)3n和安全參數(shù)t。1.隨即選取整

3、數(shù)b,22nb；2.計算nbrnmod1; 3.如果1r，則 n 是合數(shù)；4.上述過程重復(fù)t次；定義 2：合數(shù) n稱為 carmichael數(shù)，如果對所有的正整數(shù)b，(b,n)=1, 都有同余式nbnmod11成立定理 3：設(shè) n是一個奇合數(shù)。(i)如果 n被一個大于 1平方數(shù)整除，則n不是 carmichael數(shù)。(ii)如果kppn1是一個無平方數(shù)，則n 是 carmichael數(shù)的充要條件是11npi，ki1定理 4：每個 carmichael數(shù)是至少三個不同素數(shù)的乘積注：1.存在無窮多個 carmichael數(shù)2.當 n充分大時，區(qū)間n,2內(nèi)的 carmichael數(shù)的個數(shù)大于等于72

4、n6.2 euler擬素數(shù)引例：設(shè) n 是奇素數(shù)，根據(jù)定理，我們有同余式)(mod21nnbbn精品好資料 -如有侵權(quán)請聯(lián)系網(wǎng)站刪除精品好資料 -如有侵權(quán)請聯(lián)系網(wǎng)站刪除對任意整數(shù) b 成立因此，如果存在整數(shù)b，(b,n)=1,使得)(mod21nnbbn則 n 不是一個素數(shù)。定義 1:設(shè) n是一個正奇合數(shù)，設(shè)整數(shù)b與 n互素，如果整數(shù) n 和 b滿足條件：)(mod21nnbbn則 n 叫做對于基 b 的euler 擬素數(shù)。定理 1：如果 n是對于基 b的 euler 擬素數(shù)，則 n是對于基 b的擬素數(shù)。/ solovay-stassen素性檢驗給定奇整數(shù)3n和安全參數(shù)t. 1.隨即選取整數(shù)b

5、，22nb；2.計算);(mod21nbrn3.如果1r以及1nr，則 n 是合數(shù)；4.計算 jacobi符號;nbs5.如果sr，則你是合數(shù)；6.上述過程重復(fù)t次。6.3 強擬素數(shù)精品好資料 -如有侵權(quán)請聯(lián)系網(wǎng)站刪除精品好資料 -如有侵權(quán)請聯(lián)系網(wǎng)站刪除引例：設(shè) n 是正奇整數(shù)，并且有tnn21，則我們有如下因數(shù)分解式：) 1)(1() 1)(1(121221ttttnbbbbbnn因此，如果有同余式)(mod11nbn則如下同余式至少有一個成立：)(mod1)(mod1)(mod1)(mod1122nbnbnbnbttttn定義 1：設(shè) n是一個奇合數(shù)，且有表達式tnn21，其中 t為奇數(shù)，

6、設(shè)整數(shù)b 與 n 互素，如果整數(shù) n 和 b 滿足條件：)(mod1nbt或者存在一個整數(shù)，sr0使得)(mod12nbtr則 n 叫做對于基 b 的強擬素數(shù)。定理 1：存在無窮多個對于基2的強擬素數(shù)。定理 2:如果 n是對于基 b 的強擬素數(shù)， n 是對于基 b 的 euler擬素數(shù)。定理 3：設(shè) n是一個奇合數(shù)，則n是對于基 b，11nb，的強擬素數(shù)的可能性至多為25%。/ 精品好資料 -如有侵權(quán)請聯(lián)系網(wǎng)站刪除精品好資料 -如有侵權(quán)請聯(lián)系網(wǎng)站刪除miller-rabin 素性檢驗給定奇整數(shù)3n和安全參數(shù) k。寫tns21，其中 t 為奇整數(shù)。1.隨機選取整數(shù)22,nbb。2.計算)(mod0nbrt；3.(i)如果10r或10nr，則通過檢驗，可能為素數(shù)?；氐?，繼續(xù)選取另一個隨機整數(shù)22,nbb; (ii)否則，有10r以及10nr，我們計算)(mod201nrr；4.(i)如果11nr，則通過檢驗，可能為素數(shù)?；氐?，繼續(xù)選取另一個隨機整數(shù)22,nbb； (ii)否