The Applications Of Cloud Computing In Primality Testing

The Cloud brings us another information revolution. A great variety of cloud expressions came up suddenly, such as cloud storage, cloud computing, cloud security,cloud antivirus, cloud mailbox, and so on. Cloud Computing shows us selfservice, virtual resources, fast and elastic computing and mass storage, which stems from Grid Computing and Utility Computing.One of the key technologies for cloud computing is MapReduce which was proposed by Google in2009and specializes in dealing with Data-intensive computing. Actually, MapReduce had already been adopted by Apache in2006and used by Yahoo. Hadoop consists HDFS and MapReduce. The basic structure of Hadoop is splitting, split the whole task into pieces, and reduce the results after mapping. The steps for a job flow are inputting, mapping, reducing and outputting.Primality testing is one of the key technologies of RS A. The biggest prime is the47th mersenne prime (243,112,609-1), which was tested by using Lucas-Lehmer. Besides Lucas-Lehmer, there are the Sieve of Eratosthenes, Miller-Rabin, AKS and modified AKS.It’s urgent to reduce the time complexity of testing. As it is easy and precise, the Sieve of Eratosthenes has been used for a long time, but its time complexity can reach O((?)n) In2002, polynomial time complexity primality testing which is named AKS(its time complexity is O(log2n)12)was given by Agrawal, Kayal and Saxena in2002. However, we aren’t always using it. The reasons are that AKS is slower than the Sieve of Eratosthenes unless n is bigger than million and it is slower than Miller-Rabin all the time. Altough there are many modified algorithms about AKS, the Sieve of Eratosthenes and Miller-Rabin are more popular than AKS at present.With the ability of mass computing, the cloud will be adopted to detect prime, and we believe, it’11save our testing time. Now, I will show the achievements we have received:1) We have implemented some steps of primality testing by using MapReduce. The preconditions before we get started are the independence and randomness of our inputting. The iteration algorithm can’t satisfy it, so we have to find out the satisfied algorithms. After hard working, we find that there is a part of the Sieve of Eratosthenes can use MapReduce, and the same to AKS. Therefore, via screening adoptable inputting, designing Map and Reduce functions, deploying Hadoop properly, we did primality testing in the Cloud. To the other primality testing algorithms, we show the most popular testing which called Miller-Rabin and Lucas-Lehmer. Consider with its iteration, we can’t split the job flow into pieces; however, we also have other ways to develope it.2) We have given the new methods to search primes among a group of specified integers. Generally speaking, we need to find a new prime among a group of integers which we call it integer set. Our scheme is to split the integer set into pieces and allot the smaller tasks to each slave for mapping and reducing.3) We have resolved the giant integer transfer. The huge integer is hard to transfer. The integer’s decimal digit we used during our experiment is almost larger than20. Nomal VC data type can’t satisfy us. We need more powerful data type, after hard searching, we decide to use GMP.