mersenneforum.org Is there independent check for found factors?
 Register FAQ Search Today's Posts Mark Forums Read

 2011-03-01, 15:59 #1 bloodIce     Feb 2010 Sweden 17310 Posts Is there independent check for found factors? Out of curiosity I wonder if there is an Prime95 independent check that a factor is actually dividing an exponent? I guess the server checks somehow that the factor is not a mistake.
2011-03-01, 17:00   #2
chalsall
If I May

"Chris Halsall"
Sep 2002

22×7×359 Posts

Quote:
 Originally Posted by bloodIce Out of curiosity I wonder if there is an Prime95 independent check that a factor is actually dividing an exponent? I guess the server checks somehow that the factor is not a mistake.
The PrimeNet server does check that any factor reported is in fact a factor.

Factor found reports to the PrimeNet server are impossible to fake.

(There is a corollary to this, which I won't go into....)

 2011-03-04, 12:27 #3 bloodIce     Feb 2010 Sweden 173 Posts Thanks for the answer. I was more curious if it is Prime95 independent, but probably the division is trivial once you know a factor. I am not saying anything about the program, I simply like independent verifications.
 2011-03-04, 17:57 #4 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 236138 Posts The factors are stored in the database. They are publicly available. A person could write some code that fetches the exponent and factor, then checks them. My understanding is that the total time for a single PC to verify each factor for the entire database would be less than 2 months (wild guess).
2011-03-04, 21:48   #5
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

3×2,083 Posts

Quote:
 Originally Posted by bloodIce Thanks for the answer. I was more curious if it is Prime95 independent, but probably the division is trivial once you know a factor. I am not saying anything about the program, I simply like independent verifications.
PrimeNet's check is Prime95 independent; since the division is trivial, it is probably just done as a little bit of server-side PHP or ASP code in the routines that handle client communication. There is also an additional check, performed with the msieve factoring program (of no relation to Prime95) to verify that the factor reported is PRP (probably prime); if it is composite, then msieve will split it into its constituent prime factors within a minute or two. (The cofactor of the entire Mersenne number is not checked for primality because it is extremely large and this would be very time-consuming, but that's fine since as long as the factor divides the Mersenne number, it is proven composite regardless of the cofactor's primality.)

Last fiddled with by mdettweiler on 2011-03-04 at 21:49

2011-03-04, 23:51   #6
TheJudger

"Oliver"
Mar 2005
Germany

11×101 Posts

Quote:
 Originally Posted by Uncwilly The factors are stored in the database. They are publicly available. A person could write some code that fetches the exponent and factor, then checks them. My understanding is that the total time for a single PC to verify each factor for the entire database would be less than 2 months (wild guess).
Bottleneck might be fetching the database. The test itself is _VERY_ fast and simple:
Code:
o@Lysithea:~/mfaktc/defactor> time ./defactor.exe 13828261 1979553586274192263311048622055057969

The factor 1979553586274192263311048622055057969 divides 2^13828261 -1! K = 71576374870064726985954655544
The factor 1979553586274192263311048622055057969 is probably prime

real    0m0.001s
user    0m0.000s
sys     0m0.000s
The defactor.c is a straight forward implementation using GMP. I have received the source from Luigi (ET_) and modified it a little bit.

Oliver

2011-03-05, 00:20   #7
Uncwilly
6809 > 6502

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

1012310 Posts

Quote:
 Originally Posted by TheJudger Bottleneck might be fetching the database. The test itself is _VERY_ fast and simple:
I had put a sentence to that effect in my reply, but deleted it before posting (I figured a big pipe and good timing might make that not true).

 2011-03-10, 14:55 #8 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 3×1,619 Posts However, what won't be verified is NO FACTOR found results. If due to an error the software mistakenly misses a factor, the only way to verify it would be to rerun the TF....which is NOT done today unless someone chooses to do so manually or via a different program. This simply means the exponent will (unnecessarily) continue to be available to further TF / P1 / LL / DC. That was a thread a couple years ago that discussed a known bug in the factoring code in an old version but it suggests that the suspect ranges were all rerun.
2011-03-10, 22:19   #9

"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts

Quote:
 Originally Posted by petrw1 However, what won't be verified is NO FACTOR found results.
Yes, it's well known that, in general, proving a negative is difficult. :-)

Quote:
 That was a thread a couple years ago that discussed a known bug in the factoring code in an old version but it suggests that the suspect ranges were all rerun.
However, we continue to get occasional reports of factors found in P-1 that should have been found by earlier TF, so the missed-factors problem has not yet been eliminated.

See the neighboring thread "M2629093 has a factor: 63721413359381377" at http://mersenneforum.org/showthread.php?t=15318 for more discussion of the missed-factors issue. Note George's comment in post #22 and mine in post #24 about the relative merits of devoting resources to re-TFing past searches (i.e., perfectionism) versus going a bit level deeper (i.e., productivity).

Re-TFing all past searches would take the same amount of work as simply extending all previous TF by one more bit, but would be less productive. Re-TFing may find a few missed factors, but extending all past TF by one bit would find hundreds of factors. Neither would help GIMPS's throughput.

Last fiddled with by cheesehead on 2011-03-10 at 22:28

2011-03-11, 17:03   #10
petrw1
1976 Toyota Corona years forever!

"Wayne"
Nov 2006

113718 Posts

Quote:
 Originally Posted by cheesehead Yes, it's well known that, in general, proving a negative is difficult. :-)
In general yes...

 2011-03-12, 18:51 #11 lycorn     "GIMFS" Sep 2002 Oeiras, Portugal 27518 Posts

 Similar Threads Thread Thread Starter Forum Replies Last Post aketilander PrimeNet 9 2011-05-17 11:32 UberNumberGeek Factoring 6 2009-06-17 17:22 Mini-Geek No Prime Left Behind 33 2008-03-07 23:43 Matthias C. Noc PrimeNet 1 2004-09-20 17:33 alpertron ElevenSmooth 8 2003-10-15 10:29

All times are UTC. The time now is 21:50.

Mon Dec 6 21:50:29 UTC 2021 up 136 days, 16:19, 1 user, load averages: 1.98, 2.45, 2.93