On Tuesday 03 December 2002 22:31, Daran wrote: > [... snip ...] > 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).
Let's see if I get this right. Overwhelmingly, the factors produced by P-1 factoring come out because they are smooth to the limits selected. The fraction that comes out because of the extension is << 10%. To double that fraction (i.e. to increase the total number of factors found by < 10%) we have to double the stage 2 run time? Doesn't sound that great to me, even without worrying about memory considerations. If we're talking about the _extra_ computation time in stage 2 then obviously the suggestion makes a lot more sense - though I think there needs to be a careful analysis as to what the extra computation time for actual E values might be (as opposed to a rather simplistic linear model, which fails to take into account that some of the "temporaries" needed for small E probably drop out pretty well "for free"). If we _don't_ have to worry about memory, at some point it becomes cost-effective to run ECM with small limits instead of P-1 with much larger limits. And ECM can "easily" dig out some factors which are more or less inaccessible with P-1. > [... snip ... I don't disagree but the basic argument is the same as above] > > 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. That's a very small sample. Some time ago I found a considerable number of first factors for exponents in the range 100,000-150,000 using P-1 with limits up to B1=10^6, B2=25x10^6. The results.txt file doesn't record the E value used; though I did have tons of memory available (in relation to the exponent size) and seem to remember something about wondering what E=12 meant in the console output. Or maybe I'm confusing this with recollections about running ECM? My records show 67 factors found; I mailed George on one occasion because P-1 found a factor which surprised me, but I don't think it happened twice. Incidentally I found a factor only yesterday using P-1 on a production system: [Tue Dec 3 07:54:38 2002] P-1 found a factor in stage #2, B1=220000, B2=5665000. UID: beejaybee/Procyon, M17359099 has a factor: 312980494172935109497751 Again no mention of E. If it helps, this system was set up to use 384 MBytes memory. In any case this should have come out without extensions; B1=65267 B2=3077953 is sufficient to find the factor with the "standard" stage 2 algorithm. Would there be any means of retrieving actual factors found using P-1 and the E values used from the server logs? The problem otherwise is that, so far as the database is concerned, once a factor is found, nobody cares much how! Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
