Daran wrote:
>
> ----- Original Message -----
> From: "Alexander Kruppa" <[EMAIL PROTECTED]>
> To: "Daran" <[EMAIL PROTECTED]>; <[EMAIL PROTECTED]>
> Sent: Monday, December 10, 2001 12:16 AM
> Subject: Re: Mersenne: P-1 Stage 2
>
> > P-1 stage 1 computes x = a^E (mod N), where E is the product of all
> > primes and prime powers <= B1.
>
> Right. The math page says 3^(2*E*P) and neglects to mention the (mod N).
> It also doesn't make it clear that E is a product of prime *powers*, and not
> just a primordial. I didn't understand how that could work, but this makes
> rather more sense.
>
> 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.
> [...]
>
> > For each x^p_i we compute this way, we multiply this x^p_i-1 to an
> > accumulator.
>
> (Mod N) ?
Yup. We only want the final gcd with N, so all arithmetic can be done
(mod N).
>
> This generalises surely. You could have a third bound B3, and allow one
> prime between B1 & B2, and a second prime between B1 & B3. And then a
> fourth bound B4 and so on. (I'm not suggesting that it would be useful to
> implement this.)
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
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.
Alex
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
