All, What this list needs right now is a nice juicy math debate, so here goes: I was reading the faq about P-1 factoring, and it talks about constructing a 'q' that is the product of all primes less than B1 (with some multiples?) And then I read the "skip 2, test 2" comment about trial factoring and wondered:
Would it save any time to literally "skip 2, test 2" in trial factoring, by multiplying the two factors? (Does trial factoring use the FFT to do its squaring? The comment about breaking it into 32 bit chunks implies not. But if so, the modulo is free and this question is questionable : ) Right now Prime95 constructs a list of possible factors, filters it (before hand, or on-the-fly) and then uses the powering algorithm to calculate 2^p - 1 (mod q) for each factor. If p is 24 bits, the powering algorithm requires 24 squarings, from 1 to 24 doublings, and 24 comparisons -- resulting in up to 8 to 10 modulo's (not sure what the average is). Instead, take q1*q2 (after filtering) and use the powering algorithm to calculate qq = 2^p -1 (mod q1*q2). Then calculate qq (mod q1), and qq (mod q2) using the mod portion of the code. This would replace the second set of squarings, doublings, comparisons and mods with 2 comparisons and 2 mods. The trade off is you're doubling the bit length of your factor, and if the first of the pair is a factor, you've wasted some time. This could be done several ways: 1) Use sequential pairs like the above: q1*q2, q3*q4, . . . -- You may want to do 1 at a time when q*q exceeds your bit limit. 2) Use opposite q's: if you have m factors to test use q1*qm, q2*q(m-1), q3*q(m-2), . . . -- This makes all your factors roughly the same magnitude, but they're all big. 3) Use other pairings if there is an advantage (pair 1 mod 8's, pair 7 mod 8's). -- I suspect these would be dependent on the value of p. -- You wouldn't want to spend much time deciding how to group them. For any of these, you may not want to apply it to your entire list. And if k=1, (or any specific value) has a slightly higher probability of being a factor, do it alone if it isn't filtered out. It seems to me that doing what amounts to q*q mod q twice would be cheaper than the second powering sequence. And doing the first powering with twice as many bits can't be that expensive - in fact it may reduce the number of mods. I realise this won't qualify as an 'algorithmic breakthrough', even if it did double throughput (NOT likely!), but it's been bothering me for a while. Bruce Leenstra mailto:[EMAIL PROTECTED] _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
