Prime95

Prime95 [ praɪmnaɪntifaɪv ] ( prime95.exe ) is a program for Windows and Mac OS X for testing the primality of a Mersenne number using the so-called Lucas -Lehmer test. It is offered by gimps and developed by George Woltman as software for distributed computing ( distributed computing ). The software versions for GNU / Linux and FreeBSD are called MPrime [ empraɪm ] and have unlike Prime95 no graphical user interface.

The program has one of the fastest known implementations for multiplications in which it uses highly optimized processor - code for performing Fast Fourier Transforms. The associated routines are as gwnum library in the C programming available and are used by some other programs. The gwnum is free to use, but the project conditions (Software End User License Agreement "EULA") must be complied with in the search for Mersenne primes.

The code for the generation of checksums is not publicly available for security reasons.

• 2.1 Sample Division 2.1.1 trial division with graphics cards

Applications

Distributed Computing

The program can be used as software client for distributed computing ( distributed computing ) with PrimeNet, a central database operated by gimps for Mersenne primes are operated. It then connects periodically to the PrimeNet server to request new work and deliver finished results. The calculation is performed on the CPU while it is unused. An official support for GPUs does not yet exist. With CUDALucas (Lucas -Lehmer test) and mfaktc ( trial division ), however, there are two CUDA -enabled programs, the results of which are also accepted by the server. The PrimeNet has mid-2011 approximately 62 teraflops of computing power.

Stress test

From PC enthusiasts Prime95 is often used during CPU overclocking as a stability test, as the program the CPU auslastet relatively strong, resulting in a strong heat stress results, which is often the critical factor. Program internal plausibility checks the computational results provide a quality control that reveal hardware, calculation error of the overclocked computer system.

Computing power

The program can be used as a benchmark. The results can be automatically presented to the public by the PrimeNet server for comparison.

Factoring and primality testing

Prime95 can be used to factorization of numbers of the form. Normally, however, it will only search for Mersenne primes, for a = 1, b = 2 and d = -1, with exponent c prime.

The program supports the factorization:

Sample Divison

Regarding the set of all test numbers that factorization is trial division the actual Lucas- Lehmer primality test upstream to find in individual numbers relatively quickly small factors q. The factorization trial division points to numbers that are put together and therefore there are no Mersenne primes. These numbers are administered with the aid of PrimeNet server. In it the ECM test can be applied, which is possible other factors with a length to about 60 decimal places effectively. Thereafter, a transition is made to those numbers, which run through these ECM test, the number field sieve, if necessary, which is offered by the BOINC project NFS @ Home.

Trial division with graphics cards

Since the dawn of programmable graphics processors in 2000 is the possibility to use the computing power of graphics cards to calculate parallelizable arithmetic operations ( GPGPU ). In collaboration AMD, IBM, Intel and Nvidia company, the first draft for OpenCL, a programming interface has been, among other things for graphics processors, elaborated and finally submitted to the Khronos Group.

Due to the current excess of gimps computing capacity in the field trial division by GPGPU support powerful graphics cards using the mfaktc software and OpenCL, 2011 higher ceilings are used since August. As the effort of the trial division is proportional to the size factor in mfaktc, ie depends only on the size of the factor, this software is increasingly unsuited for larger factors. However, it is hardly working memory, compared to the other two factoring trial division and P1 test, ie suitable graphics card with comparatively little graphic memory enough.

P-1 - test

Regarding the set of all numbers to be tested, the P-1 test is the actual Lucas- Lehmer primality test upstream to find in individual numbers effective medium factors q. It takes place after the trial division and finds factors that are strongly composed. It is known that possible factors q must have of the structure. The part k here is mostly composed himself. The method is the factor q, as long as all factors of k is less than the so-called B1- limit are (level 1) or all but one is less than B1 and the remaining final part of factor k is less than the so-called B2 limit ( Stage 2 with B2 ≈ 30 * B1). In rare cases, factors can be found by the so-called Brent - Suyama extension but that do not meet the B2 criterion actually. The amount of calculation is dependent on the size of the exponent and the choice of B1 and B2. Level B2 requires a lot of memory.

LL test

The computationally intensive Lucas- Lehmer primality test is then only applied to the subset of all the numbers remained inconclusive for the above factorization. Normally, the allocation of numbers to be tested is carried out automatically by PrimeNet. The border, to search up to the factors in the sample division is dependent on the test number, and increases with their size. The expenses optimum upper limits are listed in the Table sample division. They are determined empirically.

ECM test

The " Elliptic Curve Method" (ECM ) is applied to numbers that are assigned by the PrimeNet server. The ECM test will be big factors q effectively with a length to about 60 decimal places. The exponents of the automatic allocation of the ECM PrimeNet server are currently seven digits. An assignment occurs only after appropriate adjustment in Prime95 or manual request via the project website. It also has a B1 and B2 boundary ( B2 = 100 * B1). Here, too, requires level B2 much memory.

Program Options

On the project 's website, in the Worker Windows (Prime95 ) or Workers ( MPrime ) are defined, what kind of work you want to get, for example, a factorization or the Lucas- Lehmer test. This can be vergenommen also in the program itself. Under Status, you can see the work that has been obtained, and the expected completion dates. The work will be saved worktodo.txt in the file. In unreserve exponent can release an exponent. The percentage of work completed is automatically forwarded to gimps, but they can also be in the program at Manual PrimeNet Communication (Advanced → Manual Communication ... ) Send manually on the site by putting a checkmark under Send new expected completion dates to server. The new completion data is sent to the server.

You can work with the program anonymously or with a GIMPS user account. The user account and computer name must be entered in the Configure PrimeNet (Test → PrimeNet ... ) window. If you want to work anonymously, you have to leave the fields empty. The results are in the file results.txt seen renovations in versions in the file whatsnew.txt.

Versions

• Version 27 (current), last version 27.9, December 12, 2012 with AVX support ( ~ 30% haste from Intel Sandy Bridge microarchitecture ( Core 2xxx / Core 3xxx ) compared to version 26)
• Version 26, last version 26.6, 4th April 2011 ( ~ 20 % acceleration for Core i generation compared to version 25)
• Version 25, last version 25.11 13 July, 2009 ( PrimeNet 5.0 protocol)
• Version 24, last version 24.14, February 2006 ( PrimeNet 4.0 protocol)