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

RE r*s = 1 mod p

Expand Messages
  • Jose Ramón Brox
    Yes, we can! You want to find the inverse of a number s modulo p. As p is prime, we have GCD(s,p) = 1 and it exists an unique inverse r
    Message 1 of 1 , May 5, 2005
    • 0 Attachment
      Yes, we can!

      You want to find the inverse of a number s modulo p. As p is prime, we have GCD(s,p) = 1
      and it exists an unique inverse r<p for s (as you said well).

      The procedure is as follows:

      1) We make use of Euclid's algorithm to find a chain of decreasing numbers a1, a2,...,a_l
      with a1 == s and a_l == 1 (p == q1*s + a_2, n == q2*a_2 + a_3, a_2 == q3*a_3 + a_4...)

      2) We do algebra with the last equation to clear the value of a_(l-1). We go through the
      chain in the bottom-up way, substituting a_(k-1) with the value in terms of a_(k), till
      you find p as a linear dependence of s and -1. Then you have the inverse of s modulo p.

      I know I don't explain it very well in english, so I will give some examples:

      a) Find the inverse of 3 (mod 5).

      1) 5 == 3*1 + 2 , 3 == 2*1 + 1 --> 2 == 3 - 1

      2) 5 == 3*1 + 2 == 3*1 + (3 - 1) == 3*(1+1) - 1 == 3*2 - 1

      Then 5 + 1 == 3*2 and 2 is the inverse of 3 modulo 5.

      b) Find the inverse of 7 (mod 24)

      1) 24 == 7*3 + 3, 7 == 3*2 + 1 --> 3 == (7 - 1) / 2

      2) 24 == 7*3 + 3 == 7*3 + (7-1) / 2 --> 24*2 == 2*7*3 + (7-1) == 7(6+1) - 1

      2*24 +1 == 7*7

      An we have that 7 is its own inverse modulo 24
      ----------------------------------------------

      I hope this helps. If it is not clear enough, I will try to explain it further.

      Jose Brox


      ----- Original Message -----
      From: "Mark Underwood" <mark.underwood@...>
      To: <primenumbers@yahoogroups.com>
      Sent: Thursday, May 05, 2005 9:41 PM
      Subject: [PrimeNumbers] r*s = 1 mod p


      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









      Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
      The Prime Pages : http://www.primepages.org/


      Yahoo! Groups Links
    Your message has been successfully submitted and would be delivered to recipients shortly.