Geoff Reynolds writes:
>I am using mprime 22.12 on a pentium 166 MMX to do trial factoring. For the
>exponents currently being assigned from primenet it takes this machine about
>12 minutes to factor from 2^57 to 2^58.
>
>I thought I would try factoring some small exponents (under 1,000,000) from
>the nofactors.zip file. I put FactorOverride=64 into prime.ini and started
>mprime as usual but progress is _much_ slower, it will take about 8 hours to
>factor from 2^57 to 2^58.
Candidate divisors of Mp must have the form q = 2*k*p + 1, so for any
upper factoring limit B, the number of candidates we need to try is
inversely proportional to the Mersenne exponent p. OTOH, using binary
exponentiation to test whether 2^p == 1 modulo q is cheaper for smaller
p, but that work scales as log2(p). Thus, the overall work to factor
to a bound B is ~ B*p/log2(p) (where B is in terms of absolute numbers,
not the number of bits.) Also note that there's a roughly 3-4x performance
hit in going above 64 bits, because one then must use multiword integer
arithmetic.
Cheers,
-Ernst
