No factors below 77 bits - Are we sure?

Raydex · 2021-02-06, 14:50

There seem to be a lot of exponents in the 109M range for which the first logged event was "No factors from 2^63 to 2^64" (example: https://www.mersenne.org/report_expo...exp_hi=&full=1) and although they have been trial-factored to 2^76 or even 2^77 without finding a factor, it appears that no one has tested the range below 2^63. An even crazier example is this: https://www.mersenne.org/report_expo...exp_hi=&full=1. Notice that unlike the first example, this example does not have bounds B1 nor B2. User "GPU Factoring" started a TF back in May, with most recent update 2021-01-30, but has never finished it. Again, it is known that no factors exist between 2^63 and 2^74, but for all we know, maybe there is a factor between 2^1 and 2^63 that has been hiding very well and evaded all previous factoring attempts. My question is: Should we take the "No factors below 2^74" with a grain of salt? Is there a chance that it may actually be incorrect? It wouldn't even be the first time, either: see https://www.mersenne.org/report_expo...4503921&full=1. In September 2015, it was TF'd to 2^67, so the top of the exponent's entry said "No factors below 2^67" for a while, until six months later, when Mark Rose found the factor 65655858100148241169, which is less than 2^66.

retina · 2021-02-06, 14:55

For factoring: No, we are not sure. It is mostly based upon trust in what people report.

There is the possibility to detect anomalies in the rate of factor finding when looking each users results. Too few factors found might indicate a hardware issue or fraud. So far, AFAIAA, no fraud has been found, but hardware issues have been identified.

ATH · 2021-02-06, 16:17

The missing trial factoring between 0 and 2^63 or 2^64 is supposed to be a primenet bug, that it is not showing, but it was done initially.
I'm not sure what caused the bug, it could not have been the conversion from primenet v4 to v5 I think, since the range 79.3M-1000M was not opened up until v5 ?
Unless factoring results for 80+M was kept somewhere else like mersenne.ca and then imported to primenet v5 back then.

I did test a range of like 1M exponents once, where I did all the missing 0 to 2^64, and I did not find any factors. But it was a tiny range compared to the whole 80M-1000M.

Prime95 / mprime could be set to do 0 to 2^64 automatically before any PRP or LL test just to be sure, since it goes so fast even on old computers. But that will not apply to all the gpuowl and CUDALucas tests.

chris2be8 · 2021-02-06, 16:24

All factors of Mersenne numbers must be of form 2kp+1 where p is the exponent. So the lowest several bits are covered by p.

And the server itself has done checks over the bottom of the range. Which should cover up to 63 bits.

And if a factor was missed by TF it could still be found by P-1. So there are not likely to be many missed factors.

Chris.

chalsall · 2021-02-06, 16:40

Quote:

Originally Posted by chris2be8

And if a factor was missed by TF it could still be found by P-1. So there are not likely to be many missed factors.

But non-zero probability.

For GIMPS' purposes, not the end of the world. This is *not* GIMFS! 9-)

The FC/DC/et al process is authoritative of primality. Worst case scenario is more of this might be done than was optimal.

Any non-nominal TF success rate of particular users is regularly reviewed. To the best of my knowledge, no intentional cheating has ever been found, although bad kit and/or code /has/ been from time-to-time.

firejuggler · 2021-02-06, 16:45

Some factor have been missed with pm-1, but only from very early version of P95/mprime.
These can be found here : https://www.mersenne.ca/p1missed.php
Around 2750 at this time

kriesel · 2021-02-06, 16:50

See what's now the last paragraph of https://www.mersenneforum.org/showpo...6&postcount=2; begins "The absence of"

Uncwilly · 2021-02-06, 17:20

To further give assurance to the data. A user known TJAOI (ranked 33 here) has been systematically going through exponents bit level by bit level doing TF and reporting factors found. Their efforts have shown that the data on PrimeNet has been usually correct, with no obvious cheating (that was no previously investigated). They continue to search for factors even if a factor has been found for an exponent. And since they are going bitwise without worrying about the extra effort it takes for smaller numbers to get to various bit levels vs higher numbers, they have provided a great check. They are now using methods other than TF for the lower ranges. Their TF software appears to be of their own design (thus providing for a good software check vs Prime95 and the various other programs that we are using.

Prime95 · 2021-02-06, 19:09

Quote:

Originally Posted by Uncwilly

To further give assurance to the data. A user known TJAOI (ranked 33 here) has been systematically going through exponents bit level by bit level doing TF and reporting factors found.

Most factoring below 2^64 was done before primenet was keeping a history. The work was done, but a hardware error or software bug could mean a factor was missed.

However, P-1 probably would have found such a small factor.

If that fails TJAOI has looked for all factors below ~2^66 for all exponents.

In conclusion, it is very highly unlikely that a tiny factor has been missed.

Batalov · 2021-02-06, 22:25

Quote:

Originally Posted by Prime95

In conclusion, it is very highly unlikely that a tiny factor has been missed.

These candidates have received a vaccine!

What is important that there are no false negatives by design. Candidates are removed with 100% evidence that they are not pregnant.
Primes will not slip through. (There will be a negligible amount of needless primality tests - if ever a factor was missed. This is very rare.)

Compare to a very curious experimental design (implemented elsewhere on the web):
1. candidates are checked for factors
2. candidates are double-checked for factors (!!)
3. if there is no quorum of 2, candidates are triple-checked for factors (!!) ... and repeat until quorum of 2
4. candidates are checked for primality ....once (!!)
Homework: What could possibly be a problem with this design?

bur · 2021-02-14, 06:54

Batalov, do you refer to Primegrid?

There's no real doublecheck anymore, but from what I read the new system provides the same level of safety.

2021-02-06, 14:50	#1
Raydex Nov 2020 Massachusetts, USA 11011₂ Posts	No factors below 77 bits - Are we sure? There seem to be a lot of exponents in the 109M range for which the first logged event was "No factors from 2^63 to 2^64" (example: https://www.mersenne.org/report_expo...exp_hi=&full=1) and although they have been trial-factored to 2^76 or even 2^77 without finding a factor, it appears that no one has tested the range below 2^63. An even crazier example is this: https://www.mersenne.org/report_expo...exp_hi=&full=1. Notice that unlike the first example, this example does not have bounds B1 nor B2. User "GPU Factoring" started a TF back in May, with most recent update 2021-01-30, but has never finished it. Again, it is known that no factors exist between 2^63 and 2^74, but for all we know, maybe there is a factor between 2^1 and 2^63 that has been hiding very well and evaded all previous factoring attempts. My question is: Should we take the "No factors below 2^74" with a grain of salt? Is there a chance that it may actually be incorrect? It wouldn't even be the first time, either: see https://www.mersenne.org/report_expo...4503921&full=1. In September 2015, it was TF'd to 2^67, so the top of the exponent's entry said "No factors below 2^67" for a while, until six months later, when Mark Rose found the factor 65655858100148241169, which is less than 2^66.

2021-02-06, 14:55	#2
retina Undefined "The unspeakable one" Jun 2006 My evil lair 1A15₁₆ Posts	For factoring: No, we are not sure. It is mostly based upon trust in what people report. There is the possibility to detect anomalies in the rate of factor finding when looking each users results. Too few factors found might indicate a hardware issue or fraud. So far, AFAIAA, no fraud has been found, but hardware issues have been identified. Last fiddled with by retina on 2021-02-06 at 14:56

2021-02-06, 16:17	#3
ATH Einyen Dec 2003 Denmark 2·17·101 Posts	The missing trial factoring between 0 and 2^63 or 2^64 is supposed to be a primenet bug, that it is not showing, but it was done initially. I'm not sure what caused the bug, it could not have been the conversion from primenet v4 to v5 I think, since the range 79.3M-1000M was not opened up until v5 ? Unless factoring results for 80+M was kept somewhere else like mersenne.ca and then imported to primenet v5 back then. I did test a range of like 1M exponents once, where I did all the missing 0 to 2^64, and I did not find any factors. But it was a tiny range compared to the whole 80M-1000M. Prime95 / mprime could be set to do 0 to 2^64 automatically before any PRP or LL test just to be sure, since it goes so fast even on old computers. But that will not apply to all the gpuowl and CUDALucas tests. Last fiddled with by ATH on 2021-02-06 at 16:21

2021-02-06, 16:45	#6
firejuggler "Vincent" Apr 2010 Over the rainbow 101101000100₂ Posts	Some factor have been missed with pm-1, but only from very early version of P95/mprime. These can be found here : https://www.mersenne.ca/p1missed.php Around 2750 at this time Last fiddled with by firejuggler on 2021-02-06 at 16:46

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Missing factors at the 'Known Factors' page	MatWur-S530113	PrimeNet	11	2009-01-21 19:08
70.0-71.0M to 63 bits	Boulder	Lone Mersenne Hunters	3	2007-11-05 06:26
41.0M to 41.1M to 63 bits	DJones	Lone Mersenne Hunters	11	2006-12-04 20:23
64 bits versus 32 bits Windows	S485122	Software	2	2006-10-31 19:14
35-35.2 to 62 bits, cont from 61 bits	Khemikal796	Lone Mersenne Hunters	12	2005-12-01 21:35

2021-02-06, 16:24	#4
chris2be8 Sep 2009 5²×97 Posts	All factors of Mersenne numbers must be of form 2kp+1 where p is the exponent. So the lowest several bits are covered by p. And the server itself has done checks over the bottom of the range. Which should cover up to 63 bits. And if a factor was missed by TF it could still be found by P-1. So there are not likely to be many missed factors. Chris.

2021-02-06, 16:50	#7
kriesel "TF79LL86GIMPS96gpu17" Mar 2017 US midwest 7,351 Posts	See what's now the last paragraph of https://www.mersenneforum.org/showpo...6&postcount=2; begins "The absence of"

2021-02-06, 17:20	#8
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 5·7·311 Posts	To further give assurance to the data. A user known TJAOI (ranked 33 here) has been systematically going through exponents bit level by bit level doing TF and reporting factors found. Their efforts have shown that the data on PrimeNet has been usually correct, with no obvious cheating (that was no previously investigated). They continue to search for factors even if a factor has been found for an exponent. And since they are going bitwise without worrying about the extra effort it takes for smaller numbers to get to various bit levels vs higher numbers, they have provided a great check. They are now using methods other than TF for the lower ranges. Their TF software appears to be of their own design (thus providing for a good software check vs Prime95 and the various other programs that we are using.

2021-02-14, 06:54	#11
bur Aug 2020 796581e-4;32539e-3 1010001101₂ Posts	Batalov, do you refer to Primegrid? There's no real doublecheck anymore, but from what I read the new system provides the same level of safety.