mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-03-01, 15:59   #1
bloodIce
 
bloodIce's Avatar
 
Feb 2010
Sweden

17310 Posts
Default 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.
bloodIce is offline   Reply With Quote
Old 2011-03-01, 17:00   #2
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

22×7×359 Posts
Default

Quote:
Originally Posted by bloodIce View Post
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....)
chalsall is online now   Reply With Quote
Old 2011-03-04, 12:27   #3
bloodIce
 
bloodIce's Avatar
 
Feb 2010
Sweden

173 Posts
Default

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.
bloodIce is offline   Reply With Quote
Old 2011-03-04, 17:57   #4
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

236138 Posts
Default

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).
Uncwilly is online now   Reply With Quote
Old 2011-03-04, 21:48   #5
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3×2,083 Posts
Default

Quote:
Originally Posted by bloodIce View Post
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
mdettweiler is offline   Reply With Quote
Old 2011-03-04, 23:51   #6
TheJudger
 
TheJudger's Avatar
 
"Oliver"
Mar 2005
Germany

11×101 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
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
TheJudger is offline   Reply With Quote
Old 2011-03-05, 00:20   #7
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

1012310 Posts
Default

Quote:
Originally Posted by TheJudger View Post
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).
Uncwilly is online now   Reply With Quote
Old 2011-03-10, 14:55   #8
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

3×1,619 Posts
Default

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.
petrw1 is online now   Reply With Quote
Old 2011-03-10, 22:19   #9
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts
Default

Quote:
Originally Posted by petrw1 View Post
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
cheesehead is offline   Reply With Quote
Old 2011-03-11, 17:03   #10
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

113718 Posts
Default

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

http://www.youtube.com/watch?v=sh163...eature=related

http://www.youtube.com/watch?v=KiIP_KDQmXs
petrw1 is online now   Reply With Quote
Old 2011-03-12, 18:51   #11
lycorn
 
lycorn's Avatar
 
"GIMFS"
Sep 2002
Oeiras, Portugal

27518 Posts
Default

lycorn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
No factors found aketilander PrimeNet 9 2011-05-17 11:32
Fermat 12 factors already found? UberNumberGeek Factoring 6 2009-06-17 17:22
easiest way to check if you found prime Mini-Geek No Prime Left Behind 33 2008-03-07 23:43
Double-Check of factors? Matthias C. Noc PrimeNet 1 2004-09-20 17:33
More factors found with a new program 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

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.