= From [EMAIL PROTECTED] Fri Feb 7 05:15:26 2003
= 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.
=
= Can someone tell me why the time difference is so great?
=
=
= Geoff.
If you are looking for divisors q of Mp, where p and q are prime, then
q must be 1 mod p. This eliminates all but (2^58 - 2^57)/p = 2^57/p
potential values of q in [2^57, 2^58]. Other tests
(e.g., skip any potential q which is 3 or 5 mod 8, skip multiples of 3)
eliminate a fixed percentage of the potential q.
The number of survivors is inversely proportional to p.
Checking whether an individual q divides 2^p - 1 takes about log2(p)
squarings modulo q. The overall cost of O(1/p) such tests is O(log(p)/p)
p p/log(p)
2^19 26000
2^21 100000
2^23 360000
2^25 1300000
A test with p near 2^19 is estimated to take 1300000/26000 = 50
times as long as one with p near 2^25 (64 times as many candidates,
19/25 times as long per candidate).
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
