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

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

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