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

Re: [PrimeNumbers] r*s = 1 mod p

Expand Messages
  • 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 1 of 2 , May 5, 2005
      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.