----- Original Message ----- From: "George Woltman" <[EMAIL PROTECTED]> To: "Daran" <[EMAIL PROTECTED]>; <[EMAIL PROTECTED]> Sent: Thursday, November 28, 2002 2:18 AM Subject: Re: Mersenne: P-1 and non k-smooth factors
> At 06:05 PM 11/27/2002 +0000, Daran wrote: > > > if (D <= 180) E = 2; > > > else if (D <= 420) E = 4; > > > else if (D <= 2310) E = 12; > > > else if (D <= 6930) E = 30; > > > else E = 48; > > > > > > >I understand why it chooses the values of D that it does, but why these > >values of E? I understand why E must be even, and that higher powers > >ought to be highly composite, but wouldn't 6 be a good intermediate > >value? 24? 60 for the top end? > > No good reason. As far as I know, there haven't been any studies on the > best values to choose for E. For 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 > B2 For 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) I can't think of any reason why either of the two algebraic factors of C when E is 6 should be any better or worse than the single irreducible factor when E=4. And there are two of them. This suggests to me that E=6 should be about twice as effective as E=4 in providing additional factors, at about twice the cost (over and above the 'cost' of E=2). If this is correct, then it will always be worth going to E=6, whenever it is worth going to E=4, (provided there is sufficient memory to do so). Turning to E=8 it is tempting to make a similar argument, that (x^4 + d^4) should be about as good as (x^4 + x^2d^2 + d^4). If so then E=8 would be three times as good as E=4 at about three times the cost. However this ignores the fact that (x^4 + d^4) is irreducible, and therefore likely to have one very large factor, (which would not be much use to us) and fewer smaller ones. OTOH an irreducible factor of order four will be better than any single factor of order two. I therefore (tentatively) conclude that E=8 will be better than twice as good as E=4, but not three times as good. With E=10, the situation is even worse. C = (x^8 + x^6d^2 + x^4d^4 + x^2d^6 + d^8), which (I think) is irreducible. It is possible that E=10 may be less effective than E=8 or even E=6. Things improve with E=12. C = (x^2 + d^2)*(x^2 + xd + d^2)*(x^2 - xd + d^2)*(x^4 - x^2d^2 + d^4) i.e. we get every extra factor produced by E=4 and E=6 and then some more, suggesting that E=12 is between four and five times as effective as E=4 at about five times the cost. In 2 out of the 29 stage 2 factors I have found so far using E=4, k has not been smooth to B2. This suggests that increasing E from 4 to 12 could yield about 20% more factors. I've done a few tests with a modified and recompiled client, which suggests that it would worth it even if E=12 yielded as few as 10% more factors, though I need to investigate this further. I freely admit this analysis is simplistic and lacks rigour. Perhaps some of the number theorists on the list could improve upon it. Regards Daran _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
