In 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.
Inverse (mod p) |
Method
Fermat's theory defines:
\(a^{N-1} = 1 \pmod N\)
This can become:
\(a^{N-2} a = 1 \pmod N\)
If can multiply both sides by \(a^{-1}\) to get:
\(a^{N-2} = a^{-1} \pmod N\)
In Go, the code for this is:
func fermatInverse(a, N *big.Int) *big.Int { two := big.NewInt(2) nMinus2 := new(big.Int).Sub(N, two) return new(big.Int).Exp(a, nMinus2, N) }
For example is we have \(val\) of 64 and \(p\) of 97:
\(val^{-1} = 64^{-1} \pmod {97} = 47\)
\( 64 \times 47 \pmod {97} = 1 \)
Code
The following is an outline of the code:
package main import ( "fmt" "math/big" "strconv" "os" ) func fermatInverse(a, N *big.Int) *big.Int { two := big.NewInt(2) nMinus2 := new(big.Int).Sub(N, two) return new(big.Int).Exp(a, nMinus2, N) } func main() { p:=97 v:=64 argCount := len(os.Args[1:]) if (argCount>0) { v,_= strconv.Atoi(os.Args[1])} if (argCount>1) { p,_= strconv.Atoi(os.Args[2])} P := big.NewInt(int64(p)) val:= big.NewInt(int64(v)) res := fermatInverse(val, P) fmt.Printf("Inverse %d (mod %d) = %s",val,P,res) }
A sample run is:
Inverse 64 (mod 97) = 47
Coding