Multiplicative inverse of n mod mIn cryptography, we often need \(n^{−1}\), which is a multiplicative inverse of n mod m, i.e. \(n/(n^{−1}) = 1 \mod m\). It is used in the calculation of the decryption key in RSA, and in other cryptography methods. With RSA, we get (e x d) mod (N) = 1, where we have e and N, and must calculate d using the multiplicative inverse of n mod m. |
Examples
The following are some examples:
- Inverse of 53 mod 120 (Ans: 77)?. Try [Check]
- Inverse of 31 mod 110 (Ans: 71)?. Try [Check]
- Inverse of 3 mod 20 (Ans: 7)?. Try RSA Ex 1 for d: [Check]
- Inverse of 7 mod 20 (Ans: 3)?. Try RSA Ex 2 for d: [Check]
- Inverse of 7 mod 120 (Ans: 103)?. Try RSA Ex 3 for d: [Check]
- Inverse of 79 mod 3220 (Ans: 1019)?. Try RSA Ex 4 for d: [Check]
- Inverse of 7 mod 880 (Ans: 503)?. Try RSA Ex 5 for d: [Check]
- Inverse of 17 mod 3120 (Ans: 2753)?. Try RSA Ex 6 for d: [Check]
For example is we have \(n\) of 53 and \(m\) of 120:
\(n^{-1} = 53^{-1} \pmod {120}\)
\( 53 \times (n^{-1}) \pmod {120} = 1 \)
Let's try 77:
\( 53 \times 77 \pmod {120} = 4081 \pmod {120} = 1 \)
Code
The following is an outline of the code:
n=53 m=120 def inv(n,m,working): max=0 val=0 if (working==True): print "Val\t(val * n) mod m" while True: val = val + 1 result = (val * n) % m if (working==True): print str(val)+"\t"+str(result) if (result==1): break if (max>1500): return(0) return val if (m<n): print "m need to be larger than n" else: print "The inverse of "+str(n)+" mod "+str(m)+ " is " + str(inv(n,m,False)) print "\nWorking out" print "Found it at "+str(inv(n,m,True))
Sample run
The following is a sample run for n of 53 and m of 120:
The inverse of 53 mod 120 is 77 Working out (we are searching for a value of 1) Val (val * n) mod m 1 53 2 106 3 39 4 92 5 25 6 78 7 11 8 64 9 117 10 50 11 103 12 36 13 89 14 22 15 75 16 8 17 61 18 114 .. 59 7 60 60 61 113 62 46 63 99 64 32 65 85 66 18 67 71 68 4 69 57 70 110 71 43 72 96 73 29 74 82 75 15 76 68 77 1 Found it at 77
Presentation
An article is [here] and a demo here: