mersenneforum.org  

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

Reply
 
Thread Tools
Old 2003-09-07, 01:58   #1
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default What ( if tracked ) is the error rate for Trial Factoring

Is an error rate for Trial Factoring tracked ?

I realize that a false negative ( small factor not found/reported, when one really exists) will eventually be covered even if it takes doing a LL.

What about a false positive ( small factor found/reported, when none exist) ?

Is it even possible for this to happen ?

Or is there some sort of very quick verification ( just do the TF calc using the factor found on the mersenne ) ?

If a factor is found and no quick verification will that be the end of work on that mersenne ? Possibly missing a mersenne prime.
dsouza123 is offline   Reply With Quote
Old 2003-09-07, 02:31   #2
GP2
 
GP2's Avatar
 
Sep 2003

22×3×5×43 Posts
Default Re: What ( if tracked ) is the error rate for Trial Factorin

Quote:
What about a false positive ( small factor found/reported, when none exist) ?

Is it even possible for this to happen ?
There are no false positives in the factors database. This can easily be verified, I just did so today on the Sep 1 data.

If you have a Linux box, you can do this verification yourself.
Basically, you just need to verify that 2p mod f == 1 using a multiple-precision arithmetic library like GNU MP. Here p is the exponent and f is the factor.

unzip factors.zip # creates the file factors.cmp
decomp -f 1 100000000 # creates the file factors (about 58 MB)
./factorverify factors
# where the program factorverify.c is attached in a later post in this thread.
# Expected output = none (no lines with false factors)

On a 2.8 GHz P4 this takes less than 20 seconds for all 2.6 million factors in the GIMPS database.


Edit: previously instead of using the factorverify.c program, this post used:

cat factors | sed -e 's/^\(.*\),\(.*\)$/(2^\1-1)%\2/' | xargs ./pexpr | grep -n -v '^0$'

# Where pexpr is a small program from the demos directory of the GMP source code.
# Previous line outputs line-number of any false-positives in the "factors" file.
# Expected output = none.

This was clumsier and slower.

Last fiddled with by GP2 on 2003-10-23 at 19:44
GP2 is offline   Reply With Quote
Old 2003-09-07, 02:34   #3
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

5·19·29 Posts
Default

There is backend verification so you cannot get false positives. False negatives I'm sure have happened but are probably relatively rare.
garo is offline   Reply With Quote
Old 2003-09-07, 03:12   #4
GP2
 
GP2's Avatar
 
Sep 2003

22×3×5×43 Posts
Default

Another question for those worried about missing Mersenne primes might be: have any exponents fallen through the cracks? That is, untested, un-trial-factored, and unassigned.

This can be verified by combining all unique exponents from:
- BAD (probably redundant, all exps in BAD should already be in LUCAS_V.TXT too)
- LUCAS_V.TXT
- HRF3.TXT
- factors (the file produced by decomp -f 1 100000000 on FACTORS.CMP)
- nofactor (the file produced by decomp -n 1 100000000 on NOFACTOR.CMP)
- status.txt (the up-to-the-hour file of all current assignments of Primenet)
- cleared.txt (the up-to-the-hour file of all current cleared exponents, probably entirely redundant unless you insist on catching any exponents cleared in the few days since the last database update of BAD, LUCAS_V.TXT etc. which occurs more or less weekly)
- a 39-line file of known Mersenne prime exponents

and comparing this combined list of exponents to a file of all prime numbers less than 100,000,000. It is very easy to generate the latter file by the way... a program like sieve2310.c by John Moyer does this in a few seconds on a 2.8 GHz P4.

The comparison can be done with standard Linux utilities like cut, sort, uniq, comm, sed.

It turns out that there are no "missing" exponents less than 79.3 M.


If we omit "nofactors" from the set of files above, we can discover if there are any exponents which have been trial-factored, but not LL tested or currently assigned by Primenet. It turns out there are indeed some, but this is easily explained as manual tests or people using non-Primenet programs like Glucas or Mlucas on ranges that George has reserved for them.

Here is the complete list of "trial-factored but not-LL-tested or currently assigned by Primenet" exponents less than M39. Nothing alarming here. On the other hand, if there was a "missing" exponent somewhere well behind the current leading edge of double-checks, it would be time for conspiracy theories.
:)


12495941
12808997
12809701
12809717
12822037
12822581
12822619
12822713
12823441
12824093
12827161
12827189
12827329
12827539
12827561
12827743
12827897
12827989
12828031
12829651
13110371

There are 20 "trial-factored but not-LL-tested or currently assigned by Primenet" exponents in the 12M range, 14 in the 13M range, 85 in the 14M range, etc.
GP2 is offline   Reply With Quote
Old 2003-09-07, 05:16   #5
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

1010110000112 Posts
Default

These are likely exponents released for manual testing by George. If they are in the nofactors database, then they have not slipped through the cracks.
garo is offline   Reply With Quote
Old 2003-10-23, 18:51   #6
GP2
 
GP2's Avatar
 
Sep 2003

22×3×5×43 Posts
Default

Attached is a C program that can be used to verify factors of Mersenne exponents. It's intended for use under Unix (and uses the GMP multiple-precision library that comes with most Linux distributions).

On a 2.8GHz Pentium 4, it verifies all 2.6 million factors in the GIMPS database in less than 20 seconds.
Attached Files
File Type: zip factorverify.zip (1.5 KB, 175 views)

Last fiddled with by GP2 on 2003-10-23 at 19:24
GP2 is offline   Reply With Quote
Old 2003-10-23, 22:26   #7
lycorn
 
lycorn's Avatar
 
Sep 2002
Oeiras, Portugal

57716 Posts
Default

Quote:

Here is the complete list of "trial-factored but not-LL-tested or currently assigned by Primenet" exponents less than M39. Nothing alarming here. On the other hand, if there was a "missing" exponent somewhere well behind the current leading edge of double-checks, it would be time for conspiracy theories.
:)


12495941
.
.
.
Actually, 12495941 has already been tested (by user Amperio) and (hopefully) successfully DCed by me. I grabbed that exponent a while ago, immediately after it had expired, but some days later it was removed from my worktodo.ini and was no longer assigned to me on the Primenet status.txt report. I suppose that the original owner finished the test, and, because I had not yet reported any work, Primenet unassigned it. As I had already started working, I kept on crunching and then sent the result by email to George so he could credit it as an early DC. Hopefully, in the next release of lucas_v.txt we will see it...
The hrf3.txt file from the 21st of September has the exponent. It had expired a couple of days before.
lycorn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Error rate plot patrik Data 109 2020-01-09 18:43
error rate and mitigation ixfd64 Hardware 4 2011-04-12 02:14
How much Trial Factoring to do? odin Software 4 2010-08-08 20:23
EFF prize and error rate S485122 PrimeNet 15 2009-01-16 11:27
Error rate for LL tests GP2 Data 5 2003-09-15 23:34

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

Mon Sep 21 17:01:36 UTC 2020 up 11 days, 14:12, 1 user, load averages: 2.07, 1.85, 1.72

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.