十二講密碼執(zhí)行上

1、第十二講 密碼執(zhí)行(上)1 在某個(gè)特定代數(shù)結(jié)構(gòu)上的密碼方案的執(zhí)行效率主要由以下幾個(gè)因素決定：參數(shù)尺寸，時(shí)間與存儲平衡，可以獲得的處理能力，以及使用的數(shù)學(xué)算法。這一講和下一講主要討論潛在用于密碼方案中代數(shù)結(jié)構(gòu)上關(guān)鍵計(jì)算的有效算法。2 這里介紹的算法因?yàn)槭菍?shí)現(xiàn)密碼系統(tǒng)的關(guān)鍵技術(shù)，所以在各種文獻(xiàn)中有廣泛研討。雖然有些文獻(xiàn)也試圖指出各種算法的優(yōu)勢所在，但是通常并沒有給出系統(tǒng)的比較。3本講提要 素?cái)?shù)問題 模冪41 素?cái)?shù)問題 51.1 Miller-Rabin 測試61.1 Miller-Rabin測試(續(xù))71.1 Miller-Rabin測試(續(xù))81.1 Miller-Rabin測試(續(xù))91.1

2、Miller-Rabin測試(續(xù))101.1 Miller-Rabin測試(續(xù))111.1 Miller-Rabin測試(續(xù))121.1 Miller-Rabin測試(續(xù))13 1.2 素?cái)?shù)產(chǎn)生 素?cái)?shù)產(chǎn)生不同于前面的素性測試，但是通常與后者密切相關(guān)。前者允許被測試整數(shù)有固定的一些方式構(gòu)造，這將有可能比隨機(jī)選擇測試整數(shù)更有效率。141.2.1 隨機(jī)搜索可能的素?cái)?shù)151.2.1 隨機(jī)搜索可能的素?cái)?shù)(續(xù))161.2.1 隨機(jī)搜索可能的素?cái)?shù)(續(xù))171.2.1 隨機(jī)搜索可能的素?cái)?shù)(續(xù))18 1.2.1 隨機(jī)搜索可能的素?cái)?shù)(續(xù))19 1.2.2 強(qiáng)素?cái)?shù)201.2.2 強(qiáng)素?cái)?shù)(續(xù))211.2.2 強(qiáng)素?cái)?shù)(續(xù))221.2.3 產(chǎn)生DSA素?cái)?shù)231.2.3 產(chǎn)生DSA素?cái)?shù)(續(xù))241.2.3 產(chǎn)生DSA素?cái)?shù)(續(xù))251.2.3 產(chǎn)生DSA素?cái)?shù)(續(xù))261.2.3 產(chǎn)生DSA素?cái)?shù)(續(xù))272 模冪282.1 問題模型2.1.1 加法鏈292.1.2加-減法鏈302.1.3 加法序列和向量加法鏈312.1.3 加法序列和向量加法鏈(續(xù))322.1.3 加法序列和向量加法鏈(續(xù))332.2 一般模冪技術(shù)2.2.1 二進(jìn)制方法342.2.1 二進(jìn)制方法(續(xù))352.2.1 二進(jìn)制方法(續(xù))362.2.1 二進(jìn)制方法(續(xù))372.2.1 二進(jìn)