mersenneforum.org Question about the process for determining primes
 Register FAQ Search Today's Posts Mark Forums Read

 2021-04-15, 16:09 #1 piforbreakfast   Oct 2020 Terre Haute, IN 6810 Posts 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
 2021-04-15, 16:36 #2 VBCurtis     "Curtis" Feb 2005 Riverside, CA 3×5×11×29 Posts 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.
2021-04-15, 19:13   #3
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

61·157 Posts

Quote:
 Originally Posted by piforbreakfast 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.

2021-04-16, 23:34   #4
piforbreakfast

Oct 2020
Terre Haute, IN

4416 Posts

Quote:
 Originally Posted by Uncwilly 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!

 2021-04-17, 01:08 #5 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 225518 Posts The process for looking for Mersenne Primes flows like this:Make a list of primes to act as the p exponent in 2p-1 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 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) 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..
 2021-04-17, 14:04 #6 LaurV Romulan Interpreter     Jun 2011 Thailand 100100111001112 Posts 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
 2021-04-17, 15:43 #7 kriesel     "TF79LL86GIMPS96gpu17" Mar 2017 US midwest 2·33·5·19 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post storm5510 Riesel Prime Search 50 2020-04-21 17:04 enzocreti enzocreti 55 2019-04-27 11:10 Madpoo Data 3 2014-11-07 23:19 Annunaki Math 37 2003-07-26 15:19 NookieN Software 5 2003-07-11 19:19

All times are UTC. The time now is 01:53.

Sat May 15 01:53:56 UTC 2021 up 36 days, 20:34, 0 users, load averages: 2.72, 2.84, 2.63