In cryptography, we often need \(x^{−1}\), and which is a multiplicative inverse of \(x \pmod p\), i.e. \( x/x^{−1} = 1 \pmod p\). It is used in the calculation of the decryption key in RSA, and in other cryptography methods. With RSA, we get \((e \times d \pmod {\varphi} =1\) = 1, where we have \(e\) and \(\varphi\), and must calculate \(d\) using the multiplicative inverse of \(e \pmod {\varphi}\).
Inverse of \(x \pmod p\) in PowerShell |
Theory
In cryptography, we often need \(x^{−1}\), and which is a multiplicative inverse of \(x \pmod p\), i.e. \( x/x^{−1} = 1 \pmod p\). It is used in the calculation of the decryption key in RSA, and in other cryptography methods. With RSA, we get \((e \times d \pmod {\varphi} =1\) = 1, where we have \(e\) and \(\varphi\), and must calculate \(d\) using the multiplicative inverse of \(e \pmod {\varphi}\).
For example is we have \(x\) of 53 and \(p\) of 120:
\(x^{-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 \)
Coding
In PowerShell, we can use Big Integers and implement the Euclidean algorithm:
function inverse_mod([BigInt] $a,[BigInt] $p){ # res = a^{-1} (mod p) $val = [BigInt]0 $nt = [BigInt]1 $r = $p $nr = $a while ($nr -ne [BigInt]0) { $q = [BigInt]::Divide($r,$nr) $val_temp = $nt $nt = [BigInt]::Subtract($val,[BigInt]::Multiply($q,$nt)) $val = $val_temp $val_temp = $nr $nr = [BigInt]::Subtract($r, [BigInt]::Multiply($q,$nr)) $r = $val_temp } if ($r -gt 1) {return -1} if ($val -lt 0) {$val = [BigInt]::Add($val,$p)} return $val }
The full coding in PowerShell is:
function inverse_mod([BigInt] $a,[BigInt] $p){ # res = a^{-1} (mod p) $val = [BigInt]0 $nt = [BigInt]1 $r = $p $nr = $a while ($nr -ne [BigInt]0) { $q = [BigInt]::Divide($r,$nr) $val_temp = $nt $nt = [BigInt]::Subtract($val,[BigInt]::Multiply($q,$nt)) $val = $val_temp $val_temp = $nr $nr = [BigInt]::Subtract($r, [BigInt]::Multiply($q,$nr)) $r = $val_temp } if ($r -gt 1) {return -1} if ($val -lt 0) {$val = [BigInt]::Add($val,$p)} return $val } $p = [BigInt]::Pow(2,255)-19 $x = 2 try { if ($Args.Count -gt 0) { $x=[BigInt]::new($Args[0]) } } catch { "Value needs to be an integer" } try { if ($Args.Count -gt 1) { $p=[BigInt]::new($Args[1]) } } catch { "Value needs to be an integer" } $inv_x=inverse_mod $x $p "x="+$x "p="+$p "`nInverse of x (mod p) is "+$inv_x $rtn=([BigInt]::Multiply($x, $inv_x)) % $p "`nx multiplied by the inverse of x (mod p) is "+$rtn if ($rtn -eq 1) { "The result is unity, and is correct" }
and a sample run for the inverse of \(31\) modulo \(2,305,843,009,213,693,952\):
x=31 p=2305843009213693952 Inverse of x (mod p) is 1115730488329206751 x multiplied by the inverse of x (mod p) is 1 The result is unity, and is correct
If we try in Python we get:
>>> x=31 >>> p=2305843009213693952 >>> inv_x=1115730488329206751 >>> (x*inv_x)% p 1