View Single Post
Old 2006-04-06, 19:29   #23
ewmayer's Avatar
Sep 2002
Rep├║blica de California

2·3·29·67 Posts

Tony Reix just brought to my attention a bug in the sieve-bit-clearing code inside Mfactor - if the NUM_SIEVING_PRIME value used by the code is such that the largest sieve prime >= Mersenne exponent p, the sieve-clearing routine winds up sending a zero argument to the 32-bit extended GCD routine used to calculate sieve bit offsets, causing an error, for instance invoking the code with

Mfactor -m 100003 -bmin 10 -bmax 50

gives the following error:

INFO: No factoring savefile t100003 found ... starting from scratch.
searching in the interval k=[0, 1475695268087040], i.e. q=[1.000000e+00, 2.951479e+20]
each of 16 (p mod 60) passes will consist of 90332172 intervals of length 272272
ERROR: eGCD called with zero input: x = 0, y = 100003
ERROR: At line 825 of file ../util.c
Assertion failed: 0
The fix is simple - in such cases the sieve-clearing routine should just skip over p as it processes the sieving primes (since p can never divide a factor candidate of form q = 2*k*p+1 anyway), and this will be included in the next release, but in the meanwhile you should be able to run any prime > 1299721 (the maximum sieving prime used when NUM_SIEVING_PRIME = 100000 as in most of the builds I posted - if you happen to have a build with the default value of NUM_SIEVING_PRIME = 50000, p must be > 611957) without problems. I'd been so focused on large p's I neglected to run some small ones.

Last fiddled with by ewmayer on 2006-04-06 at 19:38
ewmayer is offline   Reply With Quote