math/big: return nil for nonexistent ModInverse

Currently, the behavior of z.ModInverse(g, n) is undefined
when g and n are not relatively prime.  In that case, no
ModInverse exists which can be easily checked during the
computation of the ModInverse.  Because the ModInverse does
not indicate whether the inverse exists, there are reimplementations
of a "checked" ModInverse in crypto/rsa.  This change removes the
undefined behavior.  If the ModInverse does not exist, the receiver z
is unchanged and the return value is nil. This matches the behavior of
ModSqrt for the case where the square root does not exist.

name          old time/op    new time/op    delta
ModInverse-4    2.40µs ± 4%    2.22µs ± 0%   -7.74%  (p=0.016 n=5+4)

name          old alloc/op   new alloc/op   delta
ModInverse-4    1.36kB ± 0%    1.17kB ± 0%  -14.12%  (p=0.008 n=5+5)

name          old allocs/op  new allocs/op  delta
ModInverse-4      10.0 ± 0%       9.0 ± 0%  -10.00%  (p=0.008 n=5+5)

Fixes #24922

Change-Id: If7f9d491858450bdb00f1e317152f02493c9c8a8
Reviewed-on: https://go-review.googlesource.com/108996
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>

2 files changed, 28 insertions, 8 deletions

diff --git a/src/math/big/int.go b/src/math/big/int.go
index b5378dc5cc..efd3e33bfa 100644
--- a/src/math/big/int.go
+++ b/src/math/big/int.go
@@ -659,20 +659,29 @@ func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int {
 }
 
 // ModInverse sets z to the multiplicative inverse of g in the ring ℤ/nℤ
-// and returns z. If g and n are not relatively prime, the result is undefined.
+// and returns z. If g and n are not relatively prime, g has no multiplicative
+// inverse in the ring ℤ/nℤ.  In this case, z is unchanged and the return value
+// is nil.
 func (z *Int) ModInverse(g, n *Int) *Int {
 	if g.neg {
 		// GCD expects parameters a and b to be > 0.
 		var g2 Int
 		g = g2.Mod(g, n)
 	}
-	var d Int
-	d.GCD(z, nil, g, n)
-	// x and y are such that g*x + n*y = d. Since g and n are
-	// relatively prime, d = 1. Taking that modulo n results in
-	// g*x = 1, therefore x is the inverse element.
-	if z.neg {
-		z.Add(z, n)
+	var d, x Int
+	d.GCD(&x, nil, g, n)
+
+	// if and only if d==1, g and n are relatively prime
+	if d.Cmp(intOne) != 0 {
+		return nil
+	}
+
+	// x and y are such that g*x + n*y = 1, therefore x is the inverse element,
+	// but it may be negative, so convert to the range 0 <= z < |n|
+	if x.neg {
+		z.Add(&x, n)
+	} else {
+		z.Set(&x)
 	}
 	return z
 }
diff --git a/src/math/big/int_test.go b/src/math/big/int_test.go
index 270fec6b36..dd587a8a9e 100644
--- a/src/math/big/int_test.go
+++ b/src/math/big/int_test.go
@@ -1443,6 +1443,17 @@ func TestModInverse(t *testing.T) {
 	}
 }
 
+func BenchmarkModInverse(b *testing.B) {
+	p := new(Int).SetInt64(1) // Mersenne prime 2**1279 -1
+	p.abs = p.abs.shl(p.abs, 1279)
+	p.Sub(p, intOne)
+	x := new(Int).Sub(p, intOne)
+	z := new(Int)
+	for i := 0; i < b.N; i++ {
+		z.ModInverse(x, p)
+	}
+}
+
 // testModSqrt is a helper for TestModSqrt,
 // which checks that ModSqrt can compute a square-root of elt^2.
 func testModSqrt(t *testing.T, elt, mod, sq, sqrt *Int) bool {