## p1, p2 mod q^2

Expand Messages
• If 0
Message 1 of 2 , Oct 2, 2011
• 0 Attachment
If 0 < b1 < p1 < q
and 0 < b2 < p2 < q

and

b1^p1 = 1 mod q^2

and
b2^p2 = 1 mod q^2

What can we conclude about relation between p1 and p2?

Consider the case where q is prime.

It must also be true that

b1^p1 = 1 mod q
and
b2^p2 = 1 mod q.

and since q is prime, p1 divides (q-1) and
p2 divides (q-1).

If p1 is not equal to p2, then it must be that

p1*p2 divides (q-1).

which means that q would have to be much larger, perhaps out of bounds
of calculation.

Kermit
• ... Indeed. Moreover, (b1,q) and (b2,q) are Wieferich pairs with the same q. Such conjunctions are rare. Even when we find one, the probability that it solves
Message 2 of 2 , Oct 2, 2011
• 0 Attachment
Kermit Rose <kermit@...> wrote:

> b1^p1 = 1 mod q^2
> b2^p2 = 1 mod q^2

> If p1 is not equal to p2, then it must be that
> p1*p2 divides (q-1).

Indeed. Moreover, (b1,q) and (b2,q) are Wieferich pairs
with the same q. Such conjunctions are rare.
Even when we find one, the probability that it solves
our problem, with p2 > p1 > 2, is low.
If q = 2*k*p1*p2 + 1, we might guess the probability as

(p1/(q-1))*(p2/(q-1)) = 1/(2*k*(q-1))

which is why this feat has not yet been accomplished.
But that does not mean that it cannot be done.

David
Your message has been successfully submitted and would be delivered to recipients shortly.