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

r*s = 1 mod p

Expand Messages
  • Mark Underwood
    Hi all If we are given a prime p and r
    Message 1 of 2 , May 5, 2005
    • 0 Attachment
      Hi all

      If we are given a prime p and r < p, can we easily find the (unique)
      s < p such that

      r*s = 1 mod p?

      Let's assume we can. Then of course the t < p that satisfies

      r*t = n mod p

      for any n < p is exactly

      t = (s*n) mod p

      But can we find the original s (easily) in the first place?

      Mark
    • Décio Luiz Gazzoni Filho
      ... Yes, of course, that s the operation of modular inversion. You can use Euclid s extended algorithm to find it, or maybe compute r^(p-2) mod p since
      Message 2 of 2 , May 5, 2005
      • 0 Attachment
        On Thursday 05 May 2005 16:41, you wrote:
        > Hi all
        >
        > If we are given a prime p and r < p, can we easily find the (unique)
        > s < p such that
        >
        > r*s = 1 mod p?

        Yes, of course, that's the operation of modular inversion. You can use
        Euclid's extended algorithm to find it, or maybe compute r^(p-2) mod p since
        r*r^(p-2) == r^(p-1) == 1 mod p.

        > Let's assume we can. Then of course the t < p that satisfies
        >
        > r*t = n mod p
        >
        > for any n < p is exactly
        >
        > t = (s*n) mod p

        Sure, that's trivial.

        > But can we find the original s (easily) in the first place?

        You just assumed up there that it was possible. Or do you mean `more easily
        than computing rs == 1 mod p'? If so, not that I know of, unless rt < p and s
        = rt/n by exact division, but that rarely happens.

        You should be more exact in your queries, and avoid stating trivialities,
        otherwise you're just going to confuse others that try to help.

        Décio


        [Non-text portions of this message have been removed]
      Your message has been successfully submitted and would be delivered to recipients shortly.