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.
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. Clearly this can be an expensive calculation for large values of q and target, but then interatively testing all the primes isn't remarkably cheap either. _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
