- Suppose b0^p = 1 mod q, where q is prime.

Let b = (b2 q^2 + b1 q + b0)

b^2 = (b2 b0 + b1^2) q^2 + (b1 b0 ) q + b0^2 mod q^3

b^3 = (b2 b0^2 + 2 b1^2 b0) q^2 + (2 b1 b0^2) q + b0^3 mod q^3

...

b^p = J2 q^2 + J1 q + b0^p mod q^3

b^p = J2 q^2 + J1 q + 1 mod q^3

b^p = 1 mod q^3 ==> J2 q^2 + J1 q = 0 mod q^3

==> J2 q + J1 = 0 mod q^2

==> J1 = 0 mod q and J2 = 0 mod q.

Use formula for (b2 q^2 + b1 q + b0)^p to find

expansion mod q^3.

If I were more familiar with that formula, I could do it here.

Kermit - --- In primenumbers@yahoogroups.com,

Kermit Rose <kermit@...> wrote:

> Suppose b0^p = 1 mod q, where q is prime.

...

> Let b = (b2 q^2 + b1 q + b0)

> Use formula for (b2 q^2 + b1 q + b0)^p to find

Get Pari-GP to do it for you :-)

> expansion mod q^3.

> If I were more familiar with that formula,

> I could do it here.

Assuming that p|q-1, with prime q,

we simply ask for

bsol(p,q)=lift(znprimroot(q^3)^(q^2*(q-1)/p));

\\ example:

b=bsol(5,11);if(Mod(b,11^3)^5==1,print(b));

1170

David