




下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
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 強(qiáng)擬素數(shù)引例:設(shè)n是正奇整數(shù),并且有,則我們有如下因數(shù)分解式: 因此,如果有同余式 則如下同余式至少有一個成立: 定義1:設(shè)n是一個奇合數(shù),且有表達(dá)式,其中t為奇數(shù),設(shè)整數(shù)b與n互素,如果整數(shù)n和b滿足條件: 或者存在一個整數(shù),使得 則n叫做對于基b的強(qiáng)擬素數(shù)。定理1:存在無窮多個對于基2的強(qiáng)擬素數(shù)。定理2:如果n是對于基b的強(qiáng)擬素數(shù),n是對于基b的Euler擬素數(shù)。定理3:設(shè)n是一個奇合數(shù),則n是對于基b,的強(qiáng)擬素數(shù)的可能性至多為25%。/Miller-Rabin素性檢驗給定奇整數(shù)和安全參數(shù)k。寫,其中t為奇整數(shù)。1. 隨機(jī)選取整數(shù)。2. 計算;3. (i)如果或,則通過檢驗,可能為素數(shù)。回到1,繼續(xù)選取另一個隨機(jī)整數(shù); (ii)否則,有以及,我們計算;4. (i)如果,則通過檢驗,可能為素數(shù)?;氐?,繼續(xù)選取另一個隨機(jī)整數(shù); (ii)否則,有,我們計算; 如
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 安全生產(chǎn)管理機(jī)構(gòu)信息
- 陜西省咸陽市三原南郊中學(xué)2025屆物理高一第二學(xué)期期末質(zhì)量跟蹤監(jiān)視模擬試題含解析
- 重大事故隱患怎么處理
- 工貿(mào)企業(yè)事故隱患排查治理實施導(dǎo)則
- 2025屆遼寧省葫蘆島市協(xié)作校物理高一第二學(xué)期期末考試模擬試題含解析
- 安全生產(chǎn)許可證新標(biāo)準(zhǔn)
- 做好歲末年初安全生產(chǎn)工作
- 安全標(biāo)準(zhǔn)化工作計劃和措施
- 新疆維吾爾自治區(qū)吐魯番市高昌區(qū)第二中學(xué)2025年物理高二第二學(xué)期期末質(zhì)量跟蹤監(jiān)視試題含解析
- 2025屆四川省三臺縣塔山中學(xué)高二物理第二學(xué)期期末質(zhì)量跟蹤監(jiān)視試題含解析
- 2025年廣東省中考英語試題卷(含答案解析)
- 2025年吉林省中考物理試卷真題及答案詳解(精校打印版)
- 浙江省溫州市瑞安市2023-2024學(xué)年四年級下學(xué)期英語期末試卷6月(含答案)
- 2025至2030中國羅伊氏乳桿菌行業(yè)市場現(xiàn)狀分析及競爭格局與投資發(fā)展報告
- 標(biāo)準(zhǔn)的編寫講課件
- 學(xué)堂在線 護(hù)理研究方法 期末考試答案
- 2025年湖南省中考英語試卷真題(含答案解析)
- 重癥超聲在急性呼吸困難快速鑒別診斷中的應(yīng)用
- 2025年天津市中考英語真題試卷及答案
- 鄉(xiāng)鎮(zhèn)會議制度管理制度
- 2025至2030年中國電子束曝光系統(tǒng)行業(yè)市場研究分析及發(fā)展前景研判報告
評論
0/150
提交評論