Dieter Schmitt wrote:
> P-1 found a factor in stage #1, B1=25000, B2=275000.
> M4428701 has a factor: 3035629975521900014017
> It was found at stage 1 by V20 beta 4. I'd have
> expected finding factors at lower bits first.
You're misunderstanding how the p-1 algorithm works.
p-1 run to stage 1 bound B1 succeeds if any of the the
factors of the number in question is of the form
f1*f2*...*fn + 1, and all the f's are no greater than
B1. For Mersennes, things are even better: we know that
all factors of 2^p - 1 (p prime) are of the form
2*k*p + 1, i.e. we already know a priori what one of the
f's (and in fact often the largest one) must be, so
all we need is for the integer k to be B1-smooth. For the
factor F which your run found, note that
F - 1 = 2^6.3.11^2.17.53.251.283.461.4428701 = 2*k*p,
so in this case k is exceptionally smooth - had the
stage 1 limit been just B1 = 500 (say), it would have
still found this factor. Of course this analysis is
retrospective; in general k won't be this smooth,
and since the cost of running the GCD on numbers this
big is appreciable, we prefer to run p-1 to a rather
deeper bound before testing for a factor.
In your case a second stage wasn't necessary, but
in general stage 2 succeeds if k has just one factor
in the interval [B1+1, B2], and all other factors are
no greater than B1. That's because stage 2 uses a
different powering algorithm which is substantially
cheaper on a prime-for-prime basis than that used in
stage 1, but which is restricted to the case of there
being a single outlying prime. We do things this way
because a high percentage of general composites are
of this form, i.e. have only one large prime factor.
Cheers,
-Ernst
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
