PRP-1

[preda]

Originally Posted by a1call

Well, p-1 < p
and
for any given prime

p ! a^(p-1)-1 for all a coprime to p.

See Fermat's little Theorem which pops up here periodically.

Yes indeed! so 2^(p-1) - 1 has p as a factor,
and also 2^((p-1) * k) - 1 has p as a factor.

[preda]

Originally Posted by preda

Yes indeed! so 2^(p-1) - 1 has p as a factor,
and also 2^((p-1) * k) - 1 has p as a factor.

Based on this, I can do a theoretical characterization of the the strength of the PRP-1:
Doing the PRP for M(exp), we compute 3^(2^k) for all k < Exp.

In the extreme we do the "trial P-1" multiplication at every iteration of the PRP-1 (that's why this is "theoretical" vs. "practical"). So we cover all the primes p < exp.

If we start with Base=3^powerSmooth(B1), with the PRP-1 we also cover all the primes p<exp (at least individually), which is at least as strong as a P-1 test with bounds B1, and B2=Exp.

[science_man_88]

http://www.mersenneforum.org/showthread.php?t=17126 if you need it.

[preda]

Originally Posted by preda

Yes indeed! so 2^(p-1) - 1 has p as a factor,
and also 2^((p-1) * k) - 1 has p as a factor.

This also suggests a practical approach for selecting the iterations k at which to apply the "P-1 trial".

Let d(i) (i=1..n) be the divisors of k. (The divisors d(i) can be composite)

For a prime "p", we say that "k covers p" if p-1 is a divisor of k. i.e. there exists "i" such that p == d(i) + 1.

The goal becomes to build a small set of Ks that together cover all the primes < Exp (when testing M(Exp)).

[preda]

Originally Posted by preda

This also suggests a practical approach for selecting the iterations k at which to apply the "P-1 trial".

Let d(i) (i=1..n) be the divisors of k. (The divisors d(i) can be composite)

For a prime "p", we say that "k covers p" if p-1 is a divisor of k. i.e. there exists "i" such that p == d(i) + 1.

The goal becomes to build a small set of Ks that together cover all the primes < Exp (when testing M(Exp)).

A greedy approach would be: as the PRP-1 progresses, so k iterates from 1 to Exp-1, regularly select a k that covers a large number of primes not yet covered by any previously selected Ks.

the set cover(k) = {p prime, such that p-1 | k}

[science_man_88]

Originally Posted by preda

This also suggests a practical approach for selecting the iterations k at which to apply the "P-1 trial".

Let d(i) (i=1..n) be the divisors of k. (The divisors d(i) can be composite)

For a prime "p", we say that "k covers p" if p-1 is a divisor of k. i.e. there exists "i" such that p == d(i) + 1.

The goal becomes to build a small set of Ks that together cover all the primes < Exp (when testing M(Exp)).

no prime in that range can divide it.

[preda]

Originally Posted by science_man_88

no prime in that range can divide it.

In particular, any prime p is covered by k==p-1.

[science_man_88]

Originally Posted by preda

In particular, any prime p is covered by k==p-1.

my point was that no prime less than 2p+1 where p is the prime exponent can divide a Mersenne with that prime exponent. Maybe I misunderstand you.

[preda]

Originally Posted by science_man_88

my point was that no prime less than 2p+1 where p is the prime exponent can divide a Mersenne with that prime exponent. Maybe I misunderstand you.

I'm not talking about factors of M(p). I'm talking about factors that go into the Pollard's P-1 algorithm.

[science_man_88]

Originally Posted by preda

I'm not talking about factors of M(p). I'm talking about factors that go into the Pollard's P-1 algorithm.

roght but if you want to factor a mersennes using it those other types of factors only come up in composite exponents.

[preda]

Originally Posted by a1call

Well, p-1 < p
and
for any given prime

p ! a^(p-1)-1 for all a coprime to p.

See Fermat's little Theorem which pops up here periodically.

I see that for some primes p, there is k < p-1 such that p | 2^k - 1. (if k is the smallest such that p | 2^k - 1, then k | p - 1).

For which primes does this happen? (i.e. for which p prime, there exists k < p - 1 such that p | 2^k - 1)

An example is p==7, where 7 | 2^3 - 1.