RSA加密(快速冪求余)

《RSA加密(快速冪求余)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、快速冪求余算法（OJT1128）求a^b%c（這就是著名的RSA公鑰的加密方法）當(dāng)a,b很大時(shí)，直接求解這個(gè)問(wèn)題不太可能，你能想到哪些優(yōu)化呢？算法1：直觀上，也許最容易想到的是利用a*b%c=((a%c)*b)%c，這樣每一步都進(jìn)行這種處理，這就解決了a^b可能太大存不下的問(wèn)題，但這個(gè)算法的時(shí)間復(fù)雜度依然是O(n)，根本沒(méi)有得到優(yōu)化。當(dāng)b很大時(shí)運(yùn)行時(shí)間會(huì)很長(zhǎng)算法2：另一種算法利用了分治的思想，可以達(dá)到O(logn)?？梢园裝按二進(jìn)制展開為b=p(n)*2^n+p(n-1)*2^(n-1)+...+p(1)*2+p(0)其中p(i)(0<=i<=

2、n)為0或1這樣a^b=a^(p(n)*2^n+p(n-1)*2^(n-1)+...+p(1)*2+p(0))??????=a^(p(n)*2^n)*a^(p(n-1)*2^(n-1)*...*a^(p(1)*2)*a^p(0)對(duì)于p(i)=0的情況,a^p(i)*2^(i-1)=a^0=1,不用處理，我們要考慮的僅僅是p(i)=1的情況，a^(2^i)=(a^(p(i)*2(i-1)))^2(當(dāng)p(i)=1時(shí)，a^(2^i)=(a^(2(i-1)))^2)利用這一點(diǎn)，我們可以遞推地算出所有的a^(2^i)當(dāng)然由算法1的結(jié)論a*b%c=((a%

3、c)*b)%c，我們加上取模運(yùn)算a^(2^i)%c=((a^(2(i-1))%c)*a^(2(i-1)))%c于是再把所有滿足p(i)=1的a^(2^i)%c按照算法1乘起來(lái)再%c就是結(jié)果示例:3^6%7=3^(2^2)*3^(2^1)%7????=((3^(2^1))^2%7)*(3^1*3^1%7)????=(((3^1*3^1%7)%7)^2%7*2%7)%7????=(4*2)%7????=8%7????=1當(dāng)然算法可以進(jìn)一步改進(jìn)，比如二進(jìn)制的每一位不必存起來(lái)，可以邊求邊用經(jīng)改進(jìn)后代碼如下：（輸入a,k,m,求a^k%m)longf(l

4、onga,longk,longm){longb=1;while(k>=1){if(k%2==1)b=a*b%m;a=a*a%m;k=k/2;}returnb;}例題一、高級(jí)機(jī)密TimeLimit:1000MS?MemoryLimit:65536KTotalSubmit:43Accepted:16Description在很多情況下，我們需要對(duì)信息進(jìn)行加密。特別是隨著Internet的飛速發(fā)展，加密技術(shù)就顯得尤為重要。很早以前，羅馬人為了在戰(zhàn)爭(zhēng)中傳遞信息，頻繁地使用替換法進(jìn)行信息加密。然而在計(jì)算機(jī)技術(shù)高速發(fā)展的今天，這種替換法顯得不堪一擊。因此研究

5、人員正在試圖尋找一種易于編碼、但不易于解碼的編碼規(guī)則。目前比較流行的編碼規(guī)則稱為RSA，是由美國(guó)麻省理工學(xué)院的三位教授發(fā)明的。這種編碼規(guī)則是基于一種求冪取模算法的：對(duì)于給出的三個(gè)正整數(shù)a，b，c，計(jì)算a的b次方除以c的余數(shù)。你的任務(wù)是編寫一個(gè)程序，計(jì)算abmodc。Input輸入數(shù)據(jù)只有一行，依次為三個(gè)正整數(shù)a，b，c，三個(gè)正整數(shù)之間各以一個(gè)空格隔開，并且1<=a，b

6、出的三個(gè)正整數(shù)a，b，c，計(jì)算a的b次方除以c的余數(shù),即：a^bmodc//相關(guān)公式：用二進(jìn)制表示b:b=p(n)*2^n+p(n-1)*2^(n-1)+...+p(1)*2+p(0)(其中p(i)值為0或1)//則a^b=a^(p(n)*2^n+p(n-1)*2^(n-1)+...+p(1)*2+p(0))//=a^(p(n)*2^n)*a^(p(n-1)*2^(n-1))*...*a^(p(1)*2)*a^p(0)publicclassTopSecret{publicstaticvoidmain(String[]args){longa,b,

7、c;Scannerinput=newScanner(System.in);a=input.nextInt();b=input.nextInt();c=input.nextInt();System.out.println(getPowMod(a,b,c));}publicstaticlonggetPowMod(longa,longb,longc){longresult=1;while(b>=1){if(b%2==1)result=a*result%c;a=a*a%c;b/=2;//通過(guò)b/2來(lái)求得p(i)為1還是0}returnresult;}}

8、二、D:RaisingModuloNumbersTimeLimit:1000ms???CaseTimeLimit:1000ms???MemoryLim