From e21154fe31fcf9cebe5163c53b6695cfedccac34 Mon Sep 17 00:00:00 2001 From: ALTree Date: Mon, 6 Apr 2015 21:18:37 +0200 Subject: [PATCH] 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 --- src/math/big/int_test.go | 1 + src/math/big/nat.go | 7 +++++++ 2 files changed, 8 insertions(+) diff --git a/src/math/big/int_test.go b/src/math/big/int_test.go index a972a7249b..fa4ae2d311 100644 --- a/src/math/big/int_test.go +++ b/src/math/big/int_test.go @@ -525,6 +525,7 @@ var expTests = []struct { {"1234", "-1", "1", "0"}, // misc + {"5", "1", "3", "2"}, {"5", "-7", "", "1"}, {"-5", "-7", "", "1"}, {"5", "0", "", "1"}, diff --git a/src/math/big/nat.go b/src/math/big/nat.go index 2a279d186c..7157a5487b 100644 --- a/src/math/big/nat.go +++ b/src/math/big/nat.go @@ -888,6 +888,13 @@ func (z nat) expNN(x, y, m nat) nat { } // 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)) -- 2.48.1