Miller-Rabin素數(shù)檢測優(yōu)化算法研究及其并行實現(xiàn).pdf

1、密碼破譯技術(shù)的快速發(fā)展，一方面促進了學(xué)者們對加密算法的深入研究，另一方面對現(xiàn)有算法的密鑰長度，提出了更高的要求。素數(shù)，作為幾種常用加密算法的密鑰參數(shù)，研究價值不言而喻。本文以此為背景，針對素數(shù)值越大，檢測時間越長，效率越低等問題，在研究了Miller-Rabin算法基礎(chǔ)之上，通過加入預(yù)處理過程，對原算法進行了更加細致具體的優(yōu)化，減少了原算法中冪模運算的次數(shù)，從而大大提高了對于素數(shù)的檢測速度。 優(yōu)化后的算法具備數(shù)據(jù)并行性，為了更進

2、一步提高檢測效率，本文采用并行計算技術(shù)，通過服務(wù)端向客戶端發(fā)送檢測參數(shù)，利用多臺客戶端同時進行運算的方式，根據(jù)機器性能的不同分配任務(wù)量，實現(xiàn)了用N臺客戶端完成相同任務(wù)量所用時間僅為單機所用時間的1/N，即達到了并行計算的理想狀態(tài)值。系統(tǒng)的整個研究設(shè)計過程都以最大限度地壓縮通信量為基準，盡量減少通信所帶來的額外開銷，通過大素數(shù)的本地存儲以及多線程調(diào)度結(jié)合異步編程模式等多種技術(shù)手段，實現(xiàn)了素數(shù)檢測效率的更進一步提高，最后通過多項實驗對比得到