At 05:18 PM 2/16/2002 +0000, [EMAIL PROTECTED] wrote:
>So the viability of the new algorithm depends on whether we can
>compute P*F (mod 2^p-1) faster than we can compute 2^p (mod F).
To put it in perspective, let's say you are looking for 64 bit factors
of a 10,000,000 bit number.
The basic algorithm is:
Multiply 156,250 trial factors together to form a 10,000,000 bit
number.
do {
Multiply next 156,250 trial factors making 2nd 10M bit number.
Multiply the two 10,000,000 bit numbers together mod 2^P-1
} while there are more 64-bit factors
GCD (10,000,000 bit product, 2^P-1)
Looking at the inner loop the second step uses the fast LL multiply code.
On my P4-1400 this takes 0.06 seconds or 84 million clocks or (dividing
by 156,250) 538 clocks per trial factor. This is quite promising. I haven't
measured it but the current code can test one trial factor in about 4000
clocks.
The stumbling block is how can we quickly do the first step of the inner
loop - multiplying 156,250 bit trial factors together. If someone has a
clever algorithm that can do this in fewer than 3500 clocks per trial factor
then we may have an improved factoring algorithm!
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
