【摘要】：云計(jì)算的興起帶來了又一次信息革命。云儲存、云計(jì)算、云安全、云殺毒、云郵箱等等，一系列的和云有關(guān)的名詞如雨后春筍般涌現(xiàn)。云計(jì)算是網(wǎng)格計(jì)算和效用計(jì)算的變身版，為用戶提供包括自助式服務(wù)、虛擬化資源、快速彈性計(jì)算和海量存儲等諸多服務(wù)。 云計(jì)算的關(guān)鍵技術(shù)之一就是Google公司于2009年提出的MapReduce簡化分布式計(jì)算模型，這是一種專門用來處理數(shù)據(jù)密集型計(jì)算的分布式計(jì)算方法。而這種思想早在2006年就已經(jīng)在Apache公司的Hadoop產(chǎn)品中有所體現(xiàn)，并被Yahoo公司的網(wǎng)格計(jì)算團(tuán)隊(duì)采用。Hadoop主要由HDFS和MapReduce兩部分組成，其基本思想就是把龐大的數(shù)據(jù)分成小塊，分別對小塊數(shù)據(jù)化簡之后再進(jìn)行歸約�；玖鞒淌鞘紫劝褬�(biāo)準(zhǔn)輸入流中的元素分布式存儲在每個分塊（任務(wù)節(jié)點(diǎn)）中，再由主控節(jié)點(diǎn)給任務(wù)節(jié)點(diǎn)分配Map（化簡）和Reduce（歸約）任務(wù)，任務(wù)完成后由標(biāo)準(zhǔn)輸出流輸出。 素性檢測是公鑰密碼學(xué)的關(guān)鍵技術(shù)之一，目前已經(jīng)找到的最大素?cái)?shù)是第47個梅森素?cái)?shù)（243,112,6091），其素性的判定采用的是Lucas-Lehmer素性檢測法。除了判定梅森素?cái)?shù)的Lucas-Lehmer素性檢測法，目前比較流行的素性檢測方法有theSieveofEratosthenes（試除法）、Miller-Rabin素性檢測法、AKS素性檢測法及AKS的一些改進(jìn)算法。 素性判定亟待解決的問題就是如何縮短算法的時間復(fù)雜度�？紤]到簡易和精確，試除法一直被人們廣泛使用著，盡管它的算法時間復(fù)雜度達(dá)到Ο(n)。雖然2002年Agrawal、Kayal和Saxena提出了多項(xiàng)式時間算法復(fù)雜度的AKS素性檢測算法（時間算法復(fù)雜度為Ο(logn)12 2），但是AKS算法一直沒有被廣泛使用，其關(guān)鍵原因是只有當(dāng)n達(dá)到百萬數(shù)量級，AKS算法才會優(yōu)于試除法，并且對比概率性素性檢測算Miller-Rabin（時間算法復(fù)雜度為Ο(2(logn)/2)），AKS顯得太慢了。即使后人對AKS算法進(jìn)行了很多改進(jìn)，但是始終沒能夠達(dá)到滿意的效果，在實(shí)際應(yīng)用中人們?nèi)耘f普遍采用試除法和概率性素性檢測算法進(jìn)行素性判定。 考慮到云計(jì)算的海量數(shù)據(jù)處理能力，本文擬采用基于云計(jì)算的分布式并行計(jì)算方法進(jìn)行素性檢測，以縮短素性檢測時間，，提高素性檢測效率。讓?shí)渎额^角的云計(jì)算為素性的檢測奉獻(xiàn)一份力量，讓新時代的產(chǎn)物為盤根錯節(jié)的古老問題帶來柳暗花明。現(xiàn)將本文的主要成果羅列如下： 1)實(shí)現(xiàn)了傳統(tǒng)素性檢測算法中部分環(huán)節(jié)的分布式計(jì)算。分布式計(jì)算要求的是輸入流中各個元素之間的計(jì)算互不影響，并且計(jì)算和輸入輸出次序可以任意安排。在素性檢測的很多算法里都會涉及到迭代的思想，而迭代算法是不滿足進(jìn)行分布式計(jì)算的前提條件的。但通過分析研究發(fā)現(xiàn)試除素性檢測法和AKS素性檢測法中的部分循環(huán)滿足分布式計(jì)算的條件，因此可以通過選擇準(zhǔn)確的輸入文件、設(shè)計(jì)適當(dāng)?shù)腗ap和Reduce算法、合理配置Hadoop來部分實(shí)現(xiàn)這兩種確定性算法的分布式計(jì)算。對于素性檢測的其他算法，本文列出了時下流行的Miller-Rabin和Lucas-Lehmer素性檢測算法，考慮到其中的循環(huán)涉及迭代，不方便對算法中的循環(huán)進(jìn)行Map和Reduce處理，但云計(jì)算同樣可以提高這些算法的效率。 2)提出了給定范圍內(nèi)素?cái)?shù)搜索的新方法。當(dāng)需要尋找素?cái)?shù)時，我們一般都是在某個范圍內(nèi)進(jìn)行隨機(jī)查找，本文給出的改進(jìn)方案是把給定范圍內(nèi)需要查找的所有數(shù)據(jù)根據(jù)slave（任務(wù)節(jié)點(diǎn)）的數(shù)量分割成許多小塊，讓每個slave獲得一小部分?jǐn)?shù)據(jù)，然后用Miller-Rabin或者Lucas-Lehmer書寫Map函數(shù)，再分配給每一個slave，每個slave并行地完成自己分配到的任務(wù)，最后進(jìn)行Reduce處理。 3)解決了VC環(huán)境下大數(shù)處理的問題。在素性判定中，所用到的數(shù)一般都會超過20位（十進(jìn)制），用普通的數(shù)據(jù)類型已經(jīng)遠(yuǎn)遠(yuǎn)不能滿足實(shí)驗(yàn)的要求。本文通過采用GMP軟件包來進(jìn)行數(shù)據(jù)類型擴(kuò)展，解決了大數(shù)據(jù)的輸入和輸出問題。
【學(xué)位授予單位】：成都理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2012
【分類號】：O156;TP3

【參考文獻(xiàn)】

相關(guān)期刊論文 前6條

1 吉明偉;網(wǎng)格:信息孤島的克星[J];中國電子商務(wù);2002年11期

2 高晶;;“云計(jì)算”時代中社會各領(lǐng)域信息資源的整合[J];硅谷;2011年04期

3 金正平;溫巧燕;;AKS素性測定算法的一個改進(jìn)版本在PC上的實(shí)現(xiàn)[J];四川大學(xué)學(xué)報(bào)(工程科學(xué)版);2009年01期

4 王娜;范安東;黃敏;李小偉;;云計(jì)算在素性判定中的應(yīng)用[J];四川理工學(xué)院學(xué)報(bào)(自然科學(xué)版);2011年06期

5 石永進(jìn);成啟明;;稀世珍奇的梅森素?cái)?shù)[J];青少年科技博覽;2010年Z1期

6 楊柳;梅森素?cái)?shù)漫談[J];世界文化;2005年04期

相關(guān)碩士學(xué)位論文 前1條

1 王忠儒;云環(huán)境下的虛擬機(jī)監(jiān)控和服務(wù)部署關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2010年

本文編號：2563800