----- Original Message ----- From: "Alexander Kruppa" <[EMAIL PROTECTED]> To: "Daran" <[EMAIL PROTECTED]> Cc: <[EMAIL PROTECTED]> Sent: Wednesday, December 12, 2001 1:39 AM Subject: Re: Mersenne: P-1 Stage 2
> Daran wrote: > > So if we were using P-1 to factorise 1000 using B1=15 we would calculate > > > > E = 2^9 * 3^6 * 5^4 * 7^3 * 11^2 * 13^2 > > > > Or did you mean > > > > E = 2^3 * 3^2 * 5 * 7 * 11 * 13 ? > > The programmer of the P-1 algorithm is free to choose, either way will > find factors. > But in practice one uses the second alternative for efficiency. A prime > power p^n has a probability of 1/p^n of dividing a random integer, so we > include all those primes and prime powers with a probability >= 1/B1, > that is all primes and prime powers p^n <= B1. Of course. The math.htm page is misleading, both in its explanation of the algorithm, and its definition of 'smooth'. This also throws a spanner into the works of another idea I've had. [...] > Actually, it wouldn't work well. If we wanted to allow two large primes > in factor-1, one from [B1, B2] and one from [B1, B3], we have to include > all _combinations_ of such primes, i.e. > > for all p_1 in [B1, B2] > compute x^p_1 > for all p_2 in [B1, B3] > compute (x^p_1)^p_2 Which is the same as (x^p_2)^p_1, so this is easily improved by up to a factor of 2. > multiply that to accu > gcd(accu, N) > > The inner loop would be iterated (pi(B2)-pi(B1))*(pi(B3)-pi(B1)) times, > where pi(n) is the # of primes <=n, and that would be a terribly large > number. I haven't heard of a practical three-stage algorithm yet. Yes. At first I thought you could decouple the loops by replacing x with the result of the first stage 2, but of course, all those -1's spoil that idea. Still, I can't help thinking there ought to be a better way of doing it than this, though I can't see what it might be. I just feel that inside of every O(N^2) algorithm is an O(N*log2(N)) algorithm trying to get out. 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] Has this been investigated? > Alex Daran _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
