----- Original Message ----- From: "Alexander Kruppa" <[EMAIL PROTECTED]> To: "Daran" <[EMAIL PROTECTED]> Cc: <[EMAIL PROTECTED]> Sent: Saturday, December 15, 2001 2:05 AM Subject: Re: [Fwd: Mersenne: P-1 Stage 2]
> > However, there's another generalisation that occurs to me that would be > > quite cheap to implement. The purpose of stage two is to catch those > > factors which are 'just out of reach' of stage 1. However another way a > > factor could be 'just out of reach' would be if the power of exactly one of > > the primes < B1 was exactly 1 more than stage 1 would find. Stage 2 would > > find these factors *as well* if the algorithm were run for primes in [2,B2] > > instead of [B1,B2] Actually that really ought to be [2,~B2/B1] and then [B1,B2]. Another power on top of a prime in [~B2/B1,B1] will take it above B2. Since B2 is typically only an order of magnitude greater than B1 this is not going to make a lot of difference. > > Has this been investigated? > > Good point. The implementation I described finds a factor f iff the > factorization of ord(a) mod f has only primes and prime powers <= B1 and > at most one prime <= B2. > It would be more reasonable if it could have primes and prime powers <= > B1 and at most one prime _or prime power_ <= B2. That prime power has, > after all, a probability >=1/B2 of dividing a random integer. This is a generalisation of the above. > However, that is awful to implement. In stage 1, you exponentiate each > prime p by floor(log_p(B1)). In stage 2, you'd have to include small > primes p <= sqrt(B2), exponentiated by floor(log_p(B2)) - > floor(log_p(B1)). Except that for primes above ~B2/B1, this will be zero, so we could ignore them. [...] > If you want to make really sure that all powers of primes <B2 are > included, you can modify stage 1 to do so, i.e. exponentiate each prime > p<B1 by floor(log_p(B2)). This won't take a lot of extra time and is > *much* easier to implement. I agree. The question is, which algorithm gives us the greatest factors to work ratio? > Alex Daran _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
