The Prime Internet Eisenstein Search
The Prime Internet Eisenstein Search, PIES, is a long-term effort to discover prime numbers. PIES is trying to exploit a property of a small class of numbers previously overlooked by other mathematicians, called Generalized Eisenstein Fermat numbers. These numbers have the newly discovered property that they are quicker and easier to prove prime than are typical numbers. Also in their favor is the fact that they are exceptionally dense in primes, more so than the candidates in any other prime-hunting project.
The PIES Project is orchestrated by Phil Carmody, a British mathematician living and working in Finland. Phil is the mathematician who discovered, back in 2001, the first “illegal” prime. This prime number can be unpacked into the original source code for DeCSS, the software that decodes the DVD encryption scheme. He also has discovered a second prime number that actually can execute the code.
Contributors to PIES come from the US, Canada, Finland, Germany, France and a couple of other places around the world, although it is a relatively small international project. In true Linux form, the project is based all on volunteer work, runs on a small budget, is international and produces real results. The goal is pure research and somewhat esoteric—the discovery of large prime numbers of a slightly unusual form.
Prime numbers are those numbers that can be divided by 1 and themselves only. The numbers 1 and 0 are not considered prime, and the number 2 is the only even prime number. Primes are a fundamental part of our numbering system, and the search for prime numbers has fascinated mathematicians for more than two millennia. Today, prime numbers are used for public-key encryption, and large prime number searches are computationally intensive. The world's largest primes all are archived at Professor Chris Caldwell's “Prime Pages”, hosted at the University of Tennessee at Martin. Prime Pages not only archives the world's largest primes, but it also is the world's most complete resource for information on prime numbers.
The simplest method of determining whether a number is prime was understood by the ancient Greeks. Simply divide the number by primes smaller than the square root of the number being tested. Doing so finds all factors of the number; if none are found, the number is prime. This works reasonably well if your numbers are small, but when they get large, you need to be a bit smarter about how you search, calculate and prove that the number is indeed prime. Finding what you believe to be a prime number is not enough. Mathematicians are required to provide proof.
Bernard Riemann gave a lecture in 1859 in which he proposed a way to count prime numbers as a general rule. Proving what is known as the Riemann Hypothesis was one of the great mathematical challenges of the last century, and it continues to be so this century as well. Trying to figure out how many primes are in a range and what the distribution looks like within that range is an active area of research that helps drive the search for prime numbers.
Prime numbers are a kind of backbone for our number system. The use of prime numbers is more than simple intellectual play for mathematicians. Once Ron Rivest and his colleagues figured out that prime numbers were the way to make Whitfield Diffie's idea of asymmetrical, or public-key, cryptography a reality, prime numbers became indispensable. The more security required, the larger the prime numbers have to be.
The mathematics behind the PIES Project is somewhat esoteric and is explained partly on the project home page. It shares some properties with other large-prime-hunting projects, namely that it is a cyclotomic form, that is a factor of ab–1. Other cyclotomic forms are Mersennes (2p–1) and Generalized Fermat Numbers (b(2n)+1). The PIES primes are the first of the cyclotomic forms that can be found in large sizes, in large quantities and quickly but are not explicitly of the form ab–1 or ab+1. This particular PIES form, Generalized Eisenstein Fermat numbers, was first looked at in-depth by English amateur mathematician Mike Oakes several years before PIES started. But, it was because of Phil Carmody's advances in sieving—that is, quick removal of obvious non-primes because they have small, easily found factors—and fast primality testing algorithms that it became practical to look at the larger numbers with which PIES currently is working. Cyclotomic numbers are what you get from evaluating cyclotomic polynomials. The nth cyclotomic polynomial is denoted by Phi(n), and its value at b is denoted by Phi(n,b). Mersennes are Phi(p,2), and Generalized Fermat Numbers (GFNs) are Phi(2n,b). The PIES Generalized Eisenstein Fermats are Phi(3*2n,b).
Dr David Broadhurst of the Open University has been watching the development of the PIES Project with interest, although he has not devoted any cycles to it. When asked for his opinion, he said:
This is good maths, good programming and good fun. Phil Carmody managed to enliven Professor Chris Caldwell's database of the top 5,000 proven primes. Previously it consisted almost entirely of strings ending with -1 or +1, since those forms were tuned to existing primality proving programs. Now, Phil and his friends have added several hundred entries beginning with Phi, which is math-speak for a cyclotomic polynomial, albeit a rather simple one in this case, based on the cube roots of unity. Phil was able to do this without losing processing speed. In fact, he even may have gained speed on rivals, thanks to specific properties of the two cube roots of unity that are complex numbers.
Although Phil is serious about mathematics and his various projects, he does it all for fun. His somewhat unusual sense of humor can be seen on the PIES Project home page. He believes that PIES is the only distributed computing project with a project song, for example. As one might guess from how the project name doesn't quite seem to parse correctly, it is indeed a complete contrivance, done simply so that the project name was fun and the search could be “themed”. Each fixed value of n in Phi(3*2n,b) defines a band in which primes can be hunted as b varies. Phil calls the small n=13 range “cherries”, the n=14 range “peaches” and the recently started n=15 range “apples”. Only he and his girlfriend, Anna, who assists with the project's image, words and song lyrics, know what the upcoming ranges will be called.
|Dynamic DNS—an Object Lesson in Problem Solving||May 21, 2013|
|Using Salt Stack and Vagrant for Drupal Development||May 20, 2013|
|Making Linux and Android Get Along (It's Not as Hard as It Sounds)||May 16, 2013|
|Drupal Is a Framework: Why Everyone Needs to Understand This||May 15, 2013|
|Home, My Backup Data Center||May 13, 2013|
|Non-Linux FOSS: Seashore||May 10, 2013|
- Dynamic DNS—an Object Lesson in Problem Solving
- Making Linux and Android Get Along (It's Not as Hard as It Sounds)
- Using Salt Stack and Vagrant for Drupal Development
- New Products
- A Topic for Discussion - Open Source Feature-Richness?
- RSS Feeds
- Drupal Is a Framework: Why Everyone Needs to Understand This
- Validate an E-Mail Address with PHP, the Right Way
- Readers' Choice Awards
- Tech Tip: Really Simple HTTP Server with Python
- Reply to comment | Linux Journal
13 min 21 sec ago
- All the articles you talked
2 hours 36 min ago
- All the articles you talked
2 hours 40 min ago
- All the articles you talked
2 hours 41 min ago
7 hours 6 min ago
- Keeping track of IP address
8 hours 57 min ago
- Roll your own dynamic dns
14 hours 10 min ago
- Please correct the URL for Salt Stack's web site
17 hours 22 min ago
- Android is Linux -- why no better inter-operation
19 hours 37 min ago
- Connecting Android device to desktop Linux via USB
20 hours 5 min ago
Enter to Win an Adafruit Pi Cobbler Breakout Kit for Raspberry Pi
It's Raspberry Pi month at Linux Journal. Each week in May, Adafruit will be giving away a Pi-related prize to a lucky, randomly drawn LJ reader. Winners will be announced weekly.
Fill out the fields below to enter to win this week's prize-- a Pi Cobbler Breakout Kit for Raspberry Pi.
Congratulations to our winners so far:
- 5-8-13, Pi Starter Pack: Jack Davis
- 5-15-13, Pi Model B 512MB RAM: Patrick Dunn
- 5-21-13, Prototyping Pi Plate Kit: Philip Kirby
- Next winner announced on 5-27-13!
Free Webinar: Hadoop
How to Build an Optimal Hadoop Cluster to Store and Maintain Unlimited Amounts of Data Using Microservers
Realizing the promise of Apache® Hadoop® requires the effective deployment of compute, memory, storage and networking to achieve optimal results. With its flexibility and multitude of options, it is easy to over or under provision the server infrastructure, resulting in poor performance and high TCO. Join us for an in depth, technical discussion with industry experts from leading Hadoop and server companies who will provide insights into the key considerations for designing and deploying an optimal Hadoop cluster.
Some of key questions to be discussed are:
- What is the “typical” Hadoop cluster and what should be installed on the different machine types?
- Why should you consider the typical workload patterns when making your hardware decisions?
- Are all microservers created equal for Hadoop deployments?
- How do I plan for expansion if I require more compute, memory, storage or networking?