Doubt about P-1 algorithm

[ET_]

I'm stuck.

I'm trying to figure out how the P-1 algorithm works.

From the math page of the Mersenne site, i read:

We compute E - the product of all primes less than B1. Then we compute x = 3^E*2*P.

From Mersennewiki i get:

Suppose we want to find a factor of 2²⁹-1 with B1 = 10.
Then E = 2³ × 3² × 5 × 7 × 29.

I suppose that the Math page is a short summary of the algorithm, and that the Mersennewiki has the actual description.

But in the "Step 1" section, I read:

Suppose that the largest prime factor of p-1 is less than a bound B1. Then the method proceeds to compute a^E(mod N) where N is the number to factor.

E = 2^{E[SUB]2[/SUB]} * 3^{E[SUB]3[/SUB]} * 5^{E[SUB]5[/SUB]} * ... * B


where E₂ is selected so that 2^{E[SUB]2[/SUB]} is about B1 and the same for the other prime numbers. B is the greatest prime number less than or equal to B1.

while in the example B is equal to 29.

May I please have some confirmation/explanation about it?

Luigi

[science_man_88]

Originally Posted by ET_

I'm stuck.

I'm trying to figure out how the P-1 algorithm works.

From the math page of the Mersenne site, i read:



From Mersennewiki i get:



I suppose that the Math page is a short summary of the algorithm, and that the Mersennewiki has the actual description.

May I please have some confirmation/explanation about it?

Luigi

I see what you mean it makes no sense to me either, because E=#B1 ( #=primorial) in one case and not the other. the other case seems to fit E=(#B1)*2^2*3*P

[R.D. Silverman]

Originally Posted by ET_

I'm stuck.

I'm trying to figure out how the P-1 algorithm works.

From the math page of the Mersenne site, i read:



From Mersennewiki i get:



I suppose that the Math page is a short summary of the algorithm, and that the Mersennewiki has the actual description.

But in the "Step 1" section, I read:



while in the example B is equal to 29.

May I please have some confirmation/explanation about it?

Luigi

B1 = 10 is a typo.

[R.D. Silverman]

Originally Posted by R.D. Silverman

B1 = 10 is a typo.

I assume, that they are NOT using step 2 here. If they are,
B1 = 10 is OK. It just means that they used step 2 with B2 >= 30.

[ET_]

Originally Posted by R.D. Silverman

I assume, that they are NOT using step 2 here. If they are,
B1 = 10 is OK. It just means that they used step 2 with B2 >= 30.

I see, thank you!

Luigi

[science_man_88]

Originally Posted by R.D. Silverman

I assume, that they are NOT using step 2 here. If they are,
B1 = 10 is OK. It just means that they used step 2 with B2 >= 30.

B1=10 only appears to work in my mind if they use the definition of E in stage one that is at:

http://mersennewiki.org/index.php/P-1

#(B1) != #B1*2^2*3*P but then either:

http://mersennewiki.org/index.php/P-1

or

http://www.mersenne.org/various/math.php seems wrong, figured it out is it that one of them is the "trivial" case of e3=e3=e5=....=1 because really that's the only way I can figure the 2 are using the same formula.

[Mr. P-1]

Neither math page nor wiki is completely correct. The P-1 method will find a prime factor p in stage 1 if p-1 divides E. This will work however you construct E.

For arbitrary N, an optimal choice of E - one that gives you the greatest chance of success for a given amount of work - is one in which E is the product of prime powers less than some bound B1. The wiki is correct in this respect. However for the algorithm to find p, it is not sufficient "that the largest prime factor of p-1 is less than a bound B1". Rather, the largest prime power which divides p-1 must be less than B1.

Similarly, stage 2 will find p if one prime factor is p-1 is between B1 and B2, and all other prime powers dividing p-1 are less than B1.

if p-1 has known factors, for example 2q in the case of the Mersenne number Mq, the E must necessarily have these as factors, and optimally have these as additional factors.

[axn]

Remember that for mersennes, you're allowed a 'p' for free. So for 2^29-1 will use a 29. This has nothing to do with B1 or B2.

[LaurV]

@RDS: got you this time! :P you also make mistakes, unbelievable! :P
B1=10 is not a typo. The product is 2^3*3^2*5*7, the LCM of all numbers smaller then 10. "B is the greatest prime number less than or equal to B1" is right, and that is 7.

29 has nothing to do with it. 29 comes from the fact that the order of 3 in Mp is always a multiple of 2*p. Imagine you start with 3^29 instead of 3. That is all.

For example, the order of 3 in 2^11-1 is 88, because 3^88 is 1 mod 2047. If you start with 3, you have to raise it at the power of 88, but you can safely start with 3^11 (in fact 3^22) and do less iterations (translated in a much smaller B1).

Must have in mind that P-1 tries to find a factor of the order of 3. Here the prime p (29 in the example) is for free, due to the form of mersenne factors, always 2*k*p+1, so the order of 3 in any factor f of Mp is a factor of 2*k*p, assuming the factor f is prime. So it can only be a multiple of 2p, that is a multiple of p. So you rise (3^29)^E, which is 3^(E*29) and that allows you to use a smaller B1.

[ET_]

OK, now I am SURE that someone should at least update the mersennewiki page on P-1.

Back to Riesel and C&P...

Luigi

[R.D. Silverman]

Originally Posted by LaurV

@RDS: got you this time! :P you also make mistakes, unbelievable! :P
B1=10 is not a typo. The product is 2^3*3^2*5*7, the LCM of all numbers smaller then 10. "B is the greatest prime number less than or equal to B1" is right, and that is 7.

29 has nothing to do with it.

29 comes from the fact that the order of 3 in Mp is always a multiple of 2*p. Imagine you start with 3^29 instead of 3. That is all.

This is false. One can always start with some base b = a^n where n is a
large prime just less than (say) K such that n | p-1.
This is JUST A COINCIDENCE and can not be relied upon.

P-1 is intended to work with ANY base. For the given example, we can use B1 = 30 (or 29) and the algorithm will succeed, or
we can use B1 = 10, B2 = 30.

Since p-1 is divisible by 29, 29 MUST appear in E. It just happens that
from the coincidental choice of 3 as the base that 29 divides the order of 3.
(assuming that your claim is correct; I have no reason to question it)

Try this with a base other than 3, say 11. You will need to take B1 = 30
for the 1-step algorithm or B1 = 10 and B2 = 30 for the 2-step to succeed.

The bound choice for P-1 is intended to be independent of choice of base.
Sometimes, if we are lucky, the chosen base has order divisible by a large
prime that also appears in the factorization of p-1, allowing us to succeed
with a lower B1 FOR THIS CHOICE OF base. It will not be true in general.