Sorry if this is sending out twice, I wasn't sure that it got sent the
first time...
>> As I understand the Pollard P-1 algorithm, the time required for 1 bit of
>> the exponent would be equal to 1 iteration of the LL test (one squaring
>> mod Mp), so values wouldn't be that hard to create.
(timing values, for comparison with regular factoring)
>> The main problem is
>> that to get a bound of any reasonable size, and try multiple bases, you
>> are looking at a time comperable to the LL test.
(I suppose that on further investigation, with a bound value for factors of
the exponent at 10,000 we are looking at about 14,000 squarings mod Mp, which
is really not all that many)
>> Also, one of the keen
>> things about GIMPS is that in its search for primes, it came up with loads
>> of factoring data for Mersennes. However, the P-1 algorithm would make any
>> factor distribution data a lot less usable (as it would not include P with
>> P-1 having a large prime factor).
(That is to say, if the P-1 algorithm was used, it still couldn't find all the
factors <2^64, unless we are talking about incredibly high bound values)
>> On the other hand, the P-1 algorithm can take advantage of the special
>> form of Mersenne factors. We know that P-1 must be divisable by the
>> Mersenne exponent, and that in 1/2 of the cases, it is divisable by 8.
(we know that the factors must be of the form 2*k*p+1, hence the factor-1
must be divisable by 2*p, or in the form 8*n+/-1, hence the factor-1 must
be divisable by 2 or 8)
> I'm not sure that I understand what you are saying, but the
> following are a few observations that I made when I looked at the
> problem a few years ago. The major stumbling block for an efficient
> P-1 is the implementation of a time and memory efficient GCD. If one
> has a good GCD algorithm then a stage 1 only implementation becomes
> cost effective for exponents around 3 million.
> However, the cost savings is tiny, probably less than a
> percent overall. The major benifit is that one does not need to double
> check the exponent.
Yup, silly me. You are quite correct, of course, that the GCD is the
most time consuming part.
I imagine that from what you are saying, it gets more cost-effective
the higher the exponent. How does it look at around 33219281?
-Lucas
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
