theory and practice of their search

The largest prime number known at the moment consists of almost 25 million digits. Are there larger prime numbers? Of course. There are infinitely many prime numbers. Will we find a prime number larger than 25 million digits? Also yes, the search never stops. Can we take part in it? Of course, it is enough to join one of the volunteer distributed projects to search for large prime numbers.

But first, let's remember what a prime number is. It is a number that is divisible without a remainder only by itself and by one. The smallest prime number is 2, followed by 3, 5, 7, 11, 13, 17, and this list can be continued indefinitely. What is so interesting about such numbers? Because all other numbers consist of them. Prime numbers are atoms into which all other numbers can be decomposed, that is, composite numbers. This decomposition is similar to a chemical formula (one atom can appear in it several times), and it is unique for each composite number. For example, the number 12 is decomposed as 12 = 2²·3. Of course, we can write 12 = 2·6, but 6 is not a prime number, which means that after further decomposition we get 12 = 2·2·3.

But if there are infinite prime numbers, why look for the largest? Because we can. It's all about human curiosity and the excitement of discovery. Once upon a time, searching for prime numbers was a laborious process that required a lot of paper and time. But the result could be impressive. For example, the great Russian mathematician of Swiss origin Leonard Euler proved the primeness of the number 2³¹-1, and it was the largest known prime number for almost a hundred years. With the advent of electronic computers, progress accelerated dramatically. Mathematicians found ever larger prime numbers, thought about the efficiency of calculations, and came up with new algorithms that made it possible to find even larger prime numbers on the same computers. At first, the number of digits in the largest prime number was measured in hundreds, then thousands, then millions.

By now, the need for computing resources to continue the search is so great that it exceeds the capabilities of individual enthusiasts. Since this task does not promise any economic or political benefit, there is no interest from commercial or government structures. Therefore, people have begun to unite in communities of volunteer distributed computing, such as GIMPS And PrimeGrid. To join such a community, you don't need to have any special knowledge, it's enough to have a powerful computer and a desire to spend its power on finding prime numbers. All the necessary software will be provided to you.

By the way, the software used is very specific. It is designed to extract maximum performance from modern computers, uses all possible processor and video card units, and causes maximum load on all components. Sometimes it is even used for stress tests of newly assembled computers. As the developers joke: “Our software will melt your laptop and blow up your power supply!” The computing core is written using the latest sets of processor instructions, but at the same time various mathematical tricks are constantly used to speed up the calculation of specific mathematical operations. But the price for such efficiency is an extremely narrow specialization – this software is almost impossible to use for anything other than finding very large prime numbers. In addition, it is highly discouraged to try to write your own programs, at least without first studying the theory of operations on large numbers (as described, for example, in in this treatise).

There are only a few people in the community who are involved in software development. There are also a few mathematicians in the community who sometimes throw out ideas like: “Let’s look for numbers of this shape that have this property among numbers?” If the community is interested in the proposal, then the administrators and backend developers get involved, organizing a systematic search and confirming the results. As a rule, the result is the discovery of some prime number, which is immediately registered on the site. T5K.orgwhich independently records and verifies prime numbers.

If you go to this site and look at Top 20 Prime Numbersthen you can see that numbers of the type 2 dominate thereⁿ-1. Such numbers are called Mersenne numbersand the community is looking for them GIMPS. The largest known prime number is the Mersenne prime. But not only because of the success of GIMPS, but also because of the existence of the most efficient algorithms tailored exclusively for this form and implemented on both processors and video cards. Community PrimeGrid deals with numbers of other forms, the algorithms for working with which are not as efficient and are not suitable for implementation on video cards due to a number of parameters. But PrimeGrid works on proving some mathematical hypotheses, for example, on the problem of finding minimum sierpinski number. PrimeGrid's work is divided into several subprojects, and those related to mathematical hypotheses have a specific goal, after which the subproject will be closed. In addition, there are subprojects on PrimeGrid to search for relatively small prime numbers of about 600 thousand digits in length. Finding such a number is not difficult, a modern home computer can cope with this task in a few months (if you're lucky) or in a year (if you're unlucky). This allows beginners to get involved, feel the excitement and pride of having written their name on the list T5K.orgalthough it is number 4900 in the Top 5000.

An interesting feature of prime numbers is that their distribution is very similar to the distribution of random numbers. In practical terms, this means that every large number can be prime with some probability. Whether this is true or not can only be found out by checking, but this check is the most resource-intensive action. Checking one large number for primality can take from an hour to a week, depending on the size of the number and the power of your device. At the same time, there is always a chance that the check will show that the number is prime. This feature makes the search for large prime numbers similar to fishing. You can catch a huge fish 5 minutes after casting your line, or you may not catch anything for a month. Because of this, the GIMPS and PrimeGrid communities sometimes resemble communities of fishermen discussing their gear (computer hardware), places where they bite well (optimal subprojects), and fish habits (mathematical theory). In addition, each participant's contribution is taken into account, they receive points, on the basis of which the ratings and hand out painted medals. All this makes the search process fun and turns it into a full-fledged hobby. There are known cases when enthusiasts built data centers in their garages to search for prime numbers.

How is the search process organized? First of all, the form of the number is selected, that is, a formula with one variable is selected, for example 2ⁿ-1. This formula gives us a sequence in which each individual number is called a “candidate.” We must be very careful at this point, because some formulas may have an algebraic factorization, meaning that no candidate will be prime. For example, 2²ⁿ-1=(2ⁿ-1)·(2ⁿ+1). A consultation with a mathematician is necessary to confirm that there is no algebraic decomposition. Otherwise, one can spend years on initially doomed searches. It is known that a Mersenne number can only be prime when the exponent itself is prime, otherwise there is an algebraic decomposition. To emphasize this fact, Mersenne primes are denoted by the formula 2^p-1. Thus, we immediately eliminate a huge number of candidates.

But we can eliminate many more candidates. The Greek mathematician Eratosthenes is famous for calculating the diameter of the Earth quite accurately in 240 BC. But he also came up with an algorithm for finding all prime numbers that involves eliminating candidates. First, you cross out all candidates divisible by 2, then divisible by 3, then divisible by 5, and so on down the list of small primes. This algorithm is calledSieve of Eratosthenes“, and the process is “sifting”. Depending on the shape of our candidates, sifting can be done very quickly, even without calculating the candidate value itself, but only by its formula. Sifting continues until eliminating the next candidate takes more time than the primality test itself. In real projects, the sifting depth (that is, the size of small primes) exceeds 10¹⁵. In the case where the candidate dividers themselves are required to have a certain shape, the sifting depth can reach 10²⁰. For example, Mersenne numbers are lucky again, their divisors are of the form 2 p k + 1 (2^eleven-1 = (2 11 1+1) (2 11 4+1)), which allows only k to be sorted during sifting. Thanks to all these tricks, only a small part of the original list of candidates remains.

There are many different primality tests, each running at different speeds. The number of large number operations required to perform the test depends on the length of the number in bits. For the simplest tests, this dependence is linear: the number of bits equals the number of operations. In fact, we can stop at these tests, because we work with numbers from a million to 100 million bits long. Polynomial primality tests, even with a power of 2, even with a power of 1.5, become inapplicable in practice. If it takes a day to perform 100 million operations, then waiting 100 million days becomes impractical. Therefore, the most popular test for finding large prime numbers is Fermá test. The peculiarity of this test is that it always reveals prime numbers, but sometimes it can call a tricky composite number prime. The probability of such an event for large numbers is vanishingly small, but it exists. Therefore, in the English-speaking community, this test is often called PRP (from “probable prime”). However, this test is very convenient to use for distributed search, because it has reliable error protection algorithms and result certification algorithms, which is important in open communities. However, the site T5K.org does not accept numbers whose primality has not been proven. Therefore, for each probable prime number found, the next step is to perform a real, deterministic test. We will talk about the types of these tests next time.

What is the search for large prime numbers? It is a hobby that has no practical application (at least not in the next thousand years), but enriches with knowledge and practical experience. It is a community of enthusiasts scattered all over the globe. It is a few people developing incredibly complex software in their free time. It is the secrets of the universe that anyone can touch. It is a way to leave your mark on eternity.