math/big: fix Exp when exponent is 1
Fixed bug that caused Exp(x, y, m) ( i.e. x**y (mod m) ) to return x
instead of x (mod m) when y == 1. See issue page on github for more
details.
Added test case
Fixes #9826
Change-Id: Ibabb58275a20c4231c9474199b7f1c10e54241ce
Reviewed-on: https://go-review.googlesource.com/8409
Reviewed-by: Robert Griesemer <gri@golang.org>
diff --git a/src/math/big/nat.go b/src/math/big/nat.go
index 2a279d1..7157a54 100644
--- a/src/math/big/nat.go
+++ b/src/math/big/nat.go
@@ -888,6 +888,13 @@
}
// y > 0
+ // x**1 mod m == x mod m
+ if len(y) == 1 && y[0] == 1 && len(m) != 0 {
+ _, z = z.div(z, x, m)
+ return z
+ }
+ // y > 1
+
if len(m) != 0 {
// We likely end up being as long as the modulus.
z = z.make(len(m))
