mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > PrimeNet

Reply
 
Thread Tools
Old 2021-04-15, 16:09   #1
piforbreakfast
 
Oct 2020
Terre Haute, IN

22×17 Posts
Default Question about the process for determining primes

What level of exponent will be checked (2^78, maybe?) for factors before it can be determined that in fact a number is prime? I ask that because currently one of my computers is doing a double-check on an eight-digit exponent that at the moment does not have any factors that have been determined, according to mersenne.ca.:

https://www.mersenne.ca/exponent/60884413
piforbreakfast is offline   Reply With Quote
Old 2021-04-15, 16:36   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2×2,393 Posts
Default

Consider the number 143. How far do you have to check it for factors to determine if it's prime?

Either a composite number is a perfect square, or one of its factors is smaller than its square root. So, if you check all factors below a number's square root and find no factors, you have found a prime.

But, as 143 shows, no lesser check is sufficient if you intend to determine primality by factor-checking alone.
VBCurtis is offline   Reply With Quote
Old 2021-04-15, 19:13   #3
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

958210 Posts
Default

Quote:
Originally Posted by piforbreakfast View Post
What level of exponent will be checked (2^78, maybe?) for factors before it can be determined that in fact a number is prime?
https://www.mersenne.ca/exponent/60884413
Well, it looks like you or someone else just turned in a matching doublecheck of the LL test (with non-matching and non-zero bit shifts). That proves it is not prime.
https://www.mersenne.org/report_expo...0884413&full=1
74 bits is the reasonable level for the number to be factored to before switching to a primality test. It already had that done. It also had P-1 done using B1 and B2 such that there was a 4.22% chance of finding a factor, it was done between the 73 and 74 bit runs, otherwise it would have had a 3.83% chance.
Uncwilly is offline   Reply With Quote
Old 2021-04-16, 23:34   #4
piforbreakfast
 
Oct 2020
Terre Haute, IN

22×17 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
Well, it looks like you or someone else just turned in a matching doublecheck of the LL test (with non-matching and non-zero bit shifts). That proves it is not prime.
https://www.mersenne.org/report_expo...0884413&full=1
74 bits is the reasonable level for the number to be factored to before switching to a primality test. It already had that done. It also had P-1 done using B1 and B2 such that there was a 4.22% chance of finding a factor, it was done between the 73 and 74 bit runs, otherwise it would have had a 3.83% chance.
That was me that just finished the double-check, which is why I was curious about the process as it was occurring. I'm still trying to wrap my brain around a lot of the formulas and programs.

I come to this site a lot because I know I can find a lot of people here who are smarter than me, and I'm hoping it rubs off!
piforbreakfast is offline   Reply With Quote
Old 2021-04-17, 01:08   #5
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

225568 Posts
Default

The process for looking for Mersenne Primes flows like this:
  1. Make a list of primes to act as the p exponent in 2p-1
  2. Use Trial Factoring to look for factors (thus eliminating the exponent when a factor is found.
    • How far (what bit level) to do trial factoring will depend on what recource mix (CPUs, GPUs) is available, how fast TF is compared to the primality testing, and how long (on average) will it take to run the needed primality test(s) to prove it is/isn't prime.
    • Programs that can be used to TF: Prime95/mprime for CPUs (don't use it), mfact(x) type programs for GPUs, mfactor (for different kinds of CPUs), and Factor5
  3. Try some P-1 factoring (this can find factors much larger than TF in the same amount of time).
    • More memory can make a more extensive search faster.
    • Programs: Prime95, GpuOwl (more coming)
  4. Do a primality test. We used to only use the Lucas-Lehmer test (it is definitive) and do a double check to ensure that the residues match. Now we use a PRP test because: it takes about the same amount of work as an LL test, it has better error checking and correction available, and there is a technique that can be used to avoid the need to do a full double check.
    • Prime95 and GpuOwl can currently do the PRP with the error checking/correction and generate the files that are processed to prove the result is accurate.
Mersenne.org is the home of the PrimeNet server and the mother of us all.
Mersenne.ca is largely an info site. It has some helper tools. It also is coordinating TF on exponents higher than the PrimeNet server is currently handling (and are so big that we should not worry about them for several decades/centuries.
GPU72.com is a helper site that is designed to manage the TF (and P-1) work in a more complex way and squeezing the optimum amount of work out of GPUs before turn the exponents over for primality testing..
Uncwilly is offline   Reply With Quote
Old 2021-04-17, 14:04   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×17×139 Posts
Default

Very nice summary Unc.

To add to it, about half of the exponents are eliminated by TF and P-1. For the rest, PRP will be run. If PRP turns out a probable prime, LL will be run to confirm it. This is the current scenario, the rest is history.

Last fiddled with by LaurV on 2021-04-17 at 14:05
LaurV is offline   Reply With Quote
Old 2021-04-17, 15:43   #7
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

513310 Posts
Default

To clarify on TF software:
Only mfaktc on NVIDIA gpus and mfakto on AMD gpus or perhaps OpenCL supporting IGPs are worthwhile in the mersenne.org exponent range.
There are better uses for cpus: P-1, DC, PRP.
Mfactor and the slower factor5 are useful for preliminary work above the 4^32-1 range of mfaktx.

It's more like 2/3 of prime exponents get eliminated by adequate TF or P-1.

As of Jan 27 2021:

From 2 to 100M:
~10^8 natural numbers;
~94% of those are composite and eliminated as exponents;
~65.6% of the prime exponents were eliminated by finding factors with trial factoring or P-1 factoring;
that left ~1,983,000 for primality testing;
51 primes were found (~8.85 ppm of prime exponents)

From 100M to ~332M:
~232,000,000 natural numbers;
~12,100,000 primes as possible exponents, a 94.8% reduction;
~60.6% were eliminated by trial factoring and P-1 factoring by Jan 27 2021, with more remaining to do;
expected number of primes to be found among them, ~3.1;
that's 0.25 ppm of prime exponents;
effort for a 100Mdigit primality test is ~12.4 times that of a 100M exponent's test

From ~332M to 999,999,999:
~668,000,000 natural numbers;
~33,000,000 primes as possible exponents (95% reduction);
~19,000,000 already eliminated by Jan 27 2021 with trial factoring or P-1 factoring (with much more left to do; >57% reduction so far)
expected number of Mersenne primes to be found in this range ~2.83;
that's 0.086 ppm chance per prime exponent;
effort for a 999M exponent primality test is ~126. times that of a 100M exponent;
probability per unit effort of finding a new Mersenne prime near 999M is 0.0077% that of the average in the range under 100M.

Detailed tables summarizing the January 27 2021 state of http://hoegge.dk/mersenne/GIMPSstats.html are available here.

Last fiddled with by kriesel on 2021-04-17 at 15:44
kriesel is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Question about these fascinating primes storm5510 Riesel Prime Search 50 2020-04-21 17:04
A question about primes of a particular form enzocreti enzocreti 55 2019-04-27 11:10
Question about false positive process Madpoo Data 3 2014-11-07 23:19
Problem with determining squareroots in the progressions.. Annunaki Math 37 2003-07-26 15:19
Determining cause of Primenet error 29s NookieN Software 5 2003-07-11 19:19

All times are UTC. The time now is 09:33.

Sun May 16 09:33:25 UTC 2021 up 38 days, 4:14, 0 users, load averages: 1.71, 1.69, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.