View Single Post
Old 2003-03-08, 01:34   #2
cheesehead's Avatar
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default Re: About trial factoring

Originally Posted by gbvalor
It has been a hard week and now is too late in Europe
Oh, not at all -- it's never too late in Europe. :)

Is well know that for a prime p, if the Mersenne Number

Mp = 2^p - 1

is not prime and thus it has factors, they are in the form

F = k * q + 1

where q = 2 * p

I'm wonder whether we can take any advantage of this special form of
the Mersenne number factors in Trial factoring
Yes, Prime95 trial factoring has been taking advantage of that property since the very beginning.

For trial factoring, once we have a candidate for factor passing the filters:

1) F=+1 or -1 (mod 8 )
Among other shortcuts, Prime95 trial factoring considers only the 16 congruence classes mod 120 (+-1, +-7, +-17, +-23, +-31, +-41, +-47, +-49) that might contain prime Mersenne factors. Thus it skips fourteen of the mod 120 congruence classes (+-9, +-15, +-25, +-33, +-39, +-55, and +-57) which satisfy +-1 mod 8 but are never prime.

Going to mod 840 congruence classes would enable also easily skipping all multiples of 7, but I presume George analyzed that long ago and found it not worth the extra complication compared to the cost of eliminating multiples of 7 in other steps.
cheesehead is offline   Reply With Quote