diff options
| author | Brian Kessler <brian.m.kessler@gmail.com> | 2018-06-13 10:04:49 -0600 |
|---|---|---|
| committer | Robert Griesemer <gri@golang.org> | 2018-06-14 22:26:30 +0000 |
| commit | 30b045d4d1a00801b1d1fc32a910334dcd722ba6 (patch) | |
| tree | 27179fa7be8a338ec1a9baf5e435ce8a1011596f /src/math | |
| parent | e083dc6307b6593bdd44b219ffd21699d6f17fd7 (diff) | |
| download | go-30b045d4d1a00801b1d1fc32a910334dcd722ba6.tar.xz | |
math/big: handle negative exponents in Exp
For modular exponentiation, negative exponents can be handled using
the following relation.
for y < 0: x**y mod m == (x**(-1))**|y| mod m
First compute ModInverse(x, m) and then compute the exponentiation
with the absolute value of the exponent. Non-modular exponentiation
with a negative exponent still returns 1.
Fixes #25865
Change-Id: I2a35986a24794b48e549c8de935ac662d217d8a0
Reviewed-on: https://go-review.googlesource.com/118562
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
Diffstat (limited to 'src/math')
| -rw-r--r-- | src/math/big/int.go | 16 | ||||
| -rw-r--r-- | src/math/big/int_test.go | 2 |
2 files changed, 11 insertions, 7 deletions
diff --git a/src/math/big/int.go b/src/math/big/int.go index d46b5d8a86..47a288ab44 100644 --- a/src/math/big/int.go +++ b/src/math/big/int.go @@ -442,24 +442,28 @@ func (x *Int) BitLen() int { } // Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z. -// If y <= 0, the result is 1 mod |m|; if m == nil or m == 0, z = x**y. +// If m == nil or m == 0, z = x**y unless y <= 0 then z = 1. // // Modular exponentation of inputs of a particular size is not a // cryptographically constant-time operation. func (z *Int) Exp(x, y, m *Int) *Int { // See Knuth, volume 2, section 4.6.3. - var yWords nat - if !y.neg { - yWords = y.abs + xWords := x.abs + if y.neg { + if m == nil || len(m.abs) == 0 { + return z.SetInt64(1) + } + // for y < 0: x**y mod m == (x**(-1))**|y| mod m + xWords = new(Int).ModInverse(x, m).abs } - // y >= 0 + yWords := y.abs var mWords nat if m != nil { mWords = m.abs // m.abs may be nil for m == 0 } - z.abs = z.abs.expNN(x.abs, yWords, mWords) + z.abs = z.abs.expNN(xWords, yWords, mWords) z.neg = len(z.abs) > 0 && x.neg && len(yWords) > 0 && yWords[0]&1 == 1 // 0 has no sign if z.neg && len(mWords) > 0 { // make modulus result positive diff --git a/src/math/big/int_test.go b/src/math/big/int_test.go index 111e2de573..9930ed016a 100644 --- a/src/math/big/int_test.go +++ b/src/math/big/int_test.go @@ -557,7 +557,7 @@ var expTests = []struct { {"0x8000000000000000", "3", "6719", "5447"}, {"0x8000000000000000", "1000", "6719", "1603"}, {"0x8000000000000000", "1000000", "6719", "3199"}, - {"0x8000000000000000", "-1000000", "6719", "1"}, + {"0x8000000000000000", "-1000000", "6719", "3663"}, // 3663 = ModInverse(3199, 6719) Issue #25865 {"0xffffffffffffffffffffffffffffffff", "0x12345678123456781234567812345678123456789", "0x01112222333344445555666677778889", "0x36168FA1DB3AAE6C8CE647E137F97A"}, |