Jukka Santala wrote:
>Is it just me, or does factoring smaller Mersenne numbers take
>propotionally much longer? I would expect M727 to be much faster
>than the 33M range to a fixed depth, yet the opposite _seems_ to
>be true.
For any given factoring bit-depth, larger exponents will take
a shorter period than smaller exponents. This is due to the
number of potential factors that are available in at any given
depth. Each bit-depth takes twice the amount of time to test
as the previous one (ie: 2^57 takes 2x the length of 2^56)
To determine the approximate number of potential factors that
must be tested at any given depth, take the bit-size of the
first pontentail factor, 2p+1, and double for each bit-depth up
to the bit-depth you want. Finally, divide by 2 (eliminating
potentials not meeting the 8n-1 or 8n+1 rule).
So, the first potential factor of 727 would be 1455 (an 11-bit
number). Take 1 for the number of potential 11-bit factors,
and double over and over until you get where you want (2
12-bit potentials, 4 13-bit, 8 14-bit, etc.). However,
33,219,283's first potential factor is 66,438,567 (a 26-bit
number). It has 1 26-bit potential, 2 27-bit, 4 28-bit, etc.
Take these numbers and divide by 2 for the numbers of
potential factors that need testing. You can see how there
are *way* more potential 57-bit factors for 727 than 33,219,283.
NOTE: These figures are approximate as 727 may only have say
3 potential 14-bit factors to test. (Actually, it only has 2!).
It will give you a good idea of the number of potential factors
you are looking at testing for any given bit-depth though...
To illustrate better:
To test the exponent 727 at 2^57 (only 57-bit factors), you
must test approx. 7 x 10^13 potential factors.
To test the exponent 33,219,283 at 2^57 (only 57-bit factors),
you must only test approx. 2.15 x 10^9 potentail factors.
BTW, there is a more accurate way to determine the exact number
of potential factors that need to be tested at any given depth,
but requires a little more effort. And when we're talking a
difference of a couple million potential factors with a total
of 100 trillion potential factors to test, is it really
important to know the exact number??
Eric Hahn
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
