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

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

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

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

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