Loading ...
Sorry, an error occurred while loading the content.

b^p = 1 mod q^3

Expand Messages
  • Kermit Rose
    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 +
    Message 1 of 2 , Oct 2, 2011
    • 0 Attachment
      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
    • djbroadhurst
      ... Get Pari-GP to do it for you :-) 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:
      Message 2 of 2 , Oct 2, 2011
      • 0 Attachment
        --- 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
        > expansion mod q^3.
        > If I were more familiar with that formula,
        > I could do it here.

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

        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
      Your message has been successfully submitted and would be delivered to recipients shortly.