View Single Post
Old 2003-09-07, 02:31   #2
GP2's Avatar
Sep 2003

2×5×7×37 Posts
Default Re: What ( if tracked ) is the error rate for Trial Factorin

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 # 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