公鑰密碼算法是素?cái)?shù)的一個(gè)重要應(yīng)用途徑,例如經(jīng)典的RSA算法現(xiàn)已滲透到人們信息生活的各個(gè)方面,保護(hù)著用戶的信息安全。公鑰密碼算法的優(yōu)點(diǎn)在于不需要像對稱加密算法一樣采用安全的信道傳輸密鑰,但是公鑰密碼的計(jì)算開銷以及前期的素?cái)?shù)產(chǎn)生開銷都比較大。針對素?cái)?shù)產(chǎn)生開銷大這一問題,本文借助于中國剩余定理對素?cái)?shù)在多維空間中的分布規(guī)律進(jìn)行了研究,并在此基礎(chǔ)之上設(shè)計(jì)了一種相對高效的素?cái)?shù)搜索算法,能夠有效減少在一個(gè)區(qū)間內(nèi)搜索素?cái)?shù)時(shí)所需檢查整數(shù)的數(shù)量,在一定程度上減小了素?cái)?shù)搜索的負(fù)擔(dān),增加了素?cái)?shù)搜索的效率。 

【文章來源】：網(wǎng)絡(luò)安全技術(shù)與應(yīng)用. 2019,(06)

【文章頁數(shù)】：2 頁

【部分圖文】：

[0,34]區(qū)間整數(shù)映射結(jié)果

安全模型、算法與編程‖28‖數(shù)被映射到一個(gè)三維空間。由于在區(qū)間內(nèi)的數(shù)均小于M，故三元組中元素k=y/M始終為0，因此可將映射結(jié)果在1,2平面上投影，如圖1所示。如果對區(qū)間中包含大于M的數(shù)進(jìn)行映射，如將區(qū)間[0,699]中的整數(shù)進(jìn)行映射，則效果如圖2所示，此時(shí)k≥0，是k取不同值時(shí)圖1在垂直方向上的疊加。圖中用“o”標(biāo)注的位置，其坐標(biāo)(1,2)中均不含0元素，是素?cái)?shù)可能出現(xiàn)的位置，而用“×”標(biāo)注的位置，其坐標(biāo)(1,2)中至少含有一個(gè)0元素，這些位置一定不會(huì)出現(xiàn)素?cái)?shù)。圖1[0,34]區(qū)間整數(shù)映射結(jié)果圖2[0,699]區(qū)間整數(shù)映射結(jié)果從圖1、圖2可以看出，在一個(gè)區(qū)間內(nèi)搜索素?cái)?shù)時(shí)并不需要搜索全部的整數(shù)，而只需要搜索、檢查圖中由“o”標(biāo)記的映射點(diǎn)所對應(yīng)的整數(shù)即可找到該區(qū)間內(nèi)的全部素?cái)?shù)，這樣便實(shí)現(xiàn)了縮小素?cái)?shù)搜索范圍的目的，提升了算法的性能。但從圖2可以看出，實(shí)際要搜索的點(diǎn)并沒有減少很多，搜索范圍僅僅縮小到了原來的0.6857（480/700）。原因在于，算法的性能與序列的取值及元素個(gè)數(shù)均有關(guān)系，在上述例子中，為了所繪制的圖像易于理解，序列元素的個(gè)數(shù)及取值并不是最優(yōu)的，選取更優(yōu)的序列將進(jìn)一步縮小整數(shù)的搜索范圍，帶來更大的性能提升。4算法思路及性能分析由上述分析我們得知了素?cái)?shù)在多維空間中分布的大致規(guī)律，而算法也將按照此分布規(guī)律在區(qū)間中只篩選部分整數(shù)進(jìn)行檢查，以加快在區(qū)間內(nèi)的素?cái)?shù)搜索的速度。算法首先根據(jù)選定的序列構(gòu)造所有不帶0元素的序列，并利用中國剩余定理分別求解各序列所對應(yīng)同余方程組在[0,M]區(qū)間內(nèi)的解，對于得到的每一個(gè)解，都將作為一次搜索的起點(diǎn)。算法搜索過程每次都將從一個(gè)未檢查過的

潭?實(shí)際搜索整數(shù)數(shù)量搜索區(qū)間長度。當(dāng)選取的序列為{1,2,3,…,}時(shí)，一個(gè)隨機(jī)整數(shù)與中元素分別做模運(yùn)算可能產(chǎn)生的序列共有∏=1組，除去包含0元素的序列后，剩余∏(1)=1組，不難看出，對于選定的序列而言，算法的性能優(yōu)化公式為:∏(1)=1∏=1，根據(jù)公式可知道算法性能的極限為：lim→∞∏(1)=1∏=1。如果序列選取從2開始的一系列素?cái)?shù)作為其元素，選取不同的個(gè)數(shù)將對應(yīng)于不同的搜索性能，如圖3所示的是當(dāng)序列選取素?cái)?shù)集中由2開始的連續(xù)n個(gè)元素時(shí)對應(yīng)∏(1)=1∏=1的散點(diǎn)圖。該圖的最后一個(gè)點(diǎn)是當(dāng)選取從2開始的連續(xù)83個(gè)素?cái)?shù)作為序列中元素時(shí)的性能優(yōu)化程度，此時(shí)∏(1)=1∏=1=0.0946，尋找素?cái)?shù)所要搜索的整數(shù)集合已經(jīng)縮小至原來的10%以下。值得一提的是，算法前期預(yù)處理工作的時(shí)間復(fù)雜度只與序列的元素?cái)?shù)量有關(guān)，而與所要搜索區(qū)間的區(qū)間長度無關(guān)。并且預(yù)處理工作完成后，可將預(yù)處理工作的結(jié)果保留下來，以便下一次使用時(shí)可以直接導(dǎo)入程序，避免不必要的重復(fù)計(jì)算。圖3算法性能優(yōu)化程度散點(diǎn)圖分析性能優(yōu)化公式可知，隨著序列中元素越來越多，∏(1)=1∏=1越來越小，也就意味著，素?cái)?shù)可能出現(xiàn)的位置越來越少。這一分析結(jié)果間接驗(yàn)證了這樣一個(gè)事實(shí)：整數(shù)越大，其成為素?cái)?shù)的可能性就越低，同樣長度的連續(xù)區(qū)間中，數(shù)值均值越大的區(qū)間，素?cái)?shù)的個(gè)數(shù)可能越少。5算法實(shí)驗(yàn)結(jié)果及結(jié)論驗(yàn)證理解了算法的原理就可以利用具體的編程語言對算法進(jìn)行實(shí)現(xiàn)，本文結(jié)合上述理論，利用Java語言實(shí)現(xiàn)了該算法，并打印出了關(guān)鍵的數(shù)據(jù)作?

【參考文獻(xiàn)】：
期刊論文
[1]RSA算法中快速生成大素?cái)?shù)方法的改進(jìn)[J]. 王萍,廖芳燕,廖芳午,張樹貴.  重慶文理學(xué)院學(xué)報(bào)(自然科學(xué)版). 2009(03)



本文編號：3026790