Bruce Leenstra wrote: > 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?) > ... > > 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.
Sandy Harris <[EMAIL PROTECTED]> replied: >Off-the wall question dep't.: > >How does the overhead for that compare to just calculating q, the product of >all the primes of interest, and then gcd(q, target)? If you get 1, then q >and target have no common factors. If you get anything else, your result is >the product of the common factors. One of the advantages of testing each potential factor individually, or even in pairs, is you can stop when you find a factor. With the gcd method you are always testing a large number of factors. This would be great if you wanted to completely factor the composite mersennes, it probably _would_ be faster for that. You could study the distribution of factors, combine that with overhead costs and speed comparisons to come up with the optimum number of factors to test at a time. But if most of the factors are usually smaller, the gcd method would always end up being slower. Regards, Bruce Leenstra _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
