At 10:31 PM 12/3/2002 +0000, Daran wrote:
The analysis is more complex than this. It really depends on the primeFor clarity, let's write mD as x, so that for a Suyama power E, the exponent (x^E - d^E) is thrown into the mix when either x-d or x+d is prime in [B1...B2], (and only once if both are prime). This works because (provide E is even) x^E - d^E = (x-d)*(x+d)*C where C is a sum of higher order terms. The benefit of prime-pairing arises when E=2. The cost of higher E is AFAICS linear in multiplications. The benefit of higher E comes from any additional factors thrown into the mix by C. This benefit is greatest if C has factors slightly > B2For E=4, C = (x^2 + d^2) For E=6, C = (x^4 + x^2d^2 + d^4) = (x^2 + xd + d^2)*(x^2 - xd + d^2) For E=8, C = (x^2 + d^2)*(x^4 + d^4)
factorization of these algebraic factors. If an algebraic factor's prime
factorization contains factors all below B2, then the algebraic factor
does you no good.
Why not take your example:
"on an 8.1M exponent, B1=45000,
B2=731250 and varying values for D and E, I get the following results
D E Stage 2 transforms
420 2 93946
420 4 98618 (the default for my memory settings)"
and write a program that emulates stage 2's selection of (x^E - d^E), does
a prime factorization of the value, and keeps track of which factors above B2
get included. It should be possible to calculate your increased chance of finding
a factor (someone please fill in the formula here).
Then you can run this on several D,E options and compare it to your count of
FFT transforms and come up with the optimal choice of D and E.
I'd be greatly interested in such a study.
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
