Just an observation,
If you are talking about putting less than half of the candidate factors
into the modular product, i.e. stopping when you reach the square root of
Mp, then most of the time you will need to do the gcd. But if you put all
filtered factors into the modular product, at some point it will become
zero. That can even occur before you reach the square root if Mp has more
than 2 factors.
example: for p = 29, once you multiply by 2809 (k=36), your product has all
three factors in it (k = 4,19,36), which is Mp itself, and Mp mod Mp is 0.
So a crude brute-force method would be to accumulate factors until the
product became zero (composite) or you run out of factors (prime).
This requires no gcd. Personally, I think the gcd would be cheaper than the
bignum multiplies of the large half of the factors.
It would be more practical to determine some factoring limit similar to what
the trial factoring does now.
Actually, it would be smart to include a check for zero in any version of
this method. For p = 29, its stops at k=36, when the root limit is k=199,
and the max limit is k = 399. That saves 163 or 363 big multiplies.
One problem is it only gives you that last factor - the one that flipped it
to zero. You *could* store two products, then output:
"p = 29 is composite: q = 2809, prod = 39320847" and do a gcd
later.
Regards,
-Bruce
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
