is the factorisation of Mp-1 an advantage ?

[bhelmes]

A peaceful and pleasant night for you,


if I know the factorisation or a part of the factorisation of Mp-1
do I have any advantages for checking the primality ?


(Mp should be a Mersenne number)


Or in other words, is the factorisation of p-1 helpful ?



I know the theorem of Pocklington for proofing primality
https://en.wikipedia.org/wiki/Pockli...primality_test


Thanks in advance if you spend me some lines

Bernhard

[R. Gerbicz]

Originally Posted by bhelmes

if I know the factorisation or a part of the factorisation of Mp-1
do I have any advantages for checking the primality ?

Probably there is no advantage for that, but any odd factor of Mp-1 could give a non-trival factor of another Mersenne number (with prime index),
since r|Mp-1=2*(2^(p-1)-1).

[Batalov]

Originally Posted by bhelmes

Or in other words, is the factorisation of Mp-1 helpful ?

N=Mp are a beautiful example of being proven with >>33.33% N+1 factorization (indeed, 100%).
Factorization of N-1 is needless, when you have a 100% N+1 factorization.

[JeppeSN]

Agree with Batalov; for proving primality of M_p, since the full factorization of M_p + 1 is trivial, we do not gain anything from the factorization of M_p - 1.

Of course, it may be fun to find the factorization anyway; here is a factordb query for tiny examples.

/JeppeSN

[axn]

Originally Posted by JeppeSN

Of course, it may be fun to find the factorization anyway; here is a factordb query for tiny examples.

You linked to Mp-2.

[JeppeSN]

Originally Posted by axn

You linked to Mp-2.

Oops, that is right. It should have been 2^n-2 for n prime, or 2*(2^(n-1) - 1). /JeppeSN