ONJava.com -- The Independent Source for Enterprise Java
oreilly.comSafari Books Online.Conferences.

advertisement

AddThis Social Bookmark Button

Web Services and the Search for Really Big Prime Numbers

by Eoin Lane
08/29/2002

What do searching for extraterrestrials, curing cancer, and finding big prime numbers all have in common? These problems are all being attacked with grid computing, a a technique of breaking a large problem into small tasks that can be computed independently. While projects like Seti@home and The Greatest Internet Mersenne Prime Search have received plenty of press for using the Internet to distribute tasks to end users around the globe, grid computing also takes place in more controlled environments, such as research and financial settings. But it is by using the power of the Internet and the ability to discover and access idle processes on users' machines that grid computing (once called distributed computing), can access massive numbers of machines and processes.

What does all this have to do with Web services? The grid's principal tasks -- discovery and utilization of idle processes -- are best done over a ubiquitous protocol like HTTP. Although not tied to HTTP, Web services are effectively synonymous with HTTP and allow middleware components to be invoked using a verbose ASCII-formatted message. Web services provide a framework that is ideal for grid computing architectures. The Web services framework consists of UDDI for lookup and discovery, WSDL for service definition, and SOAP/HTTP for service invocation.

In this article, this Web services framework will be applied to the problem of factorizing large numbers to check if they are prime. The problem must first be understood in terms of the mathematics behind it. This problem will then be conceptualized and remodeled in UML, and finally the problem implemented in a service-oriented manner that can easily be translated to a grid computing architecture for scalability and rapid solution of the complex problem.

Source Code

Download the source for this program. For future updates, see primes.sourceforge.net.

To this end, we'll explore the factorization of Mersenne numbers. Mersenne numbers are numbers of the type 2k-1 where p=1,2,3 ... but the real challenge here is to find Mersenne prime numbers -- that is, Mersenne numbers that are prime. These are currently the biggest known prime numbers. Let's begin with a bit of math.

The Problem

In this article, four types of numbers will be considered: prime numbers, Mersenne numbers, Mersenne prime numbers, and perfect numbers.

A prime number is any number that is only divisible by itself and one. Examples of prime numbers are 1, 2, 3, 5, 7, and 11.

A Mersenne number is a number that can be written in the form of 2k-1. The first few Mersenne numbers are 1, 3 , 7, 15, 31, 63, 127, 255, and 511.

A Mersenne Prime Number is a special type of Mersenne number, in that it is also a prime number. The first few Mersenne primes (where k = 2, 3, 5, and 7) are 3, 7, 31, and 127.

A perfect number, on the other hand is one that is equal to the sum of it parts. Put another way, a whole number is perfect if it is equal to the sum of its proper divisors. So, for example, the number 6 is perfect, because its proper divisors are 1, 2, and 3, and 1 + 2 + 3 = 6. Also perfect are 28 (1 + 2 + 4 + 7 + 14), 496, and 8128. These numbers constitute the first four perfect numbers; as is evident, there are not a lot of them.

So what is the relationship between these numbers? By definition, a Mersenne prime is also a prime number. A consequence of this is that k in the 2k-1 equation must also be prime. Also, a relationship between prime numbers and perfect numbers has been known since antiquity and was formulated by Euclid in the following theorem: If 2k-1 is prime, and if n = 2k-1(2k-1), then n is perfect.

But it wasn't until almost 2000 years later that the exact relationship between these types of numbers was resolved by Euler, in the following theorem: If n is an even perfect number, then n = 2k-1(2k-1), where 2k-1 is prime.

In plain language, an even perfect number has a Mersenne prime associated with it.

Pages: 1, 2, 3, 4, 5

Next Pagearrow