diff options
author | Adam Langley <agl@golang.org> | 2010-05-26 15:58:58 -0400 |
---|---|---|
committer | Adam Langley <agl@golang.org> | 2010-05-26 15:58:58 -0400 |
commit | f199f292e72b97aa0efffb64e5d058e61c5aa682 (patch) | |
tree | c1e8a764badaccc1957e6990b9e2ca465296035a | |
parent | 5b779284783fffdc1f573811b2b792fd83dea347 (diff) | |
download | go-f199f292e72b97aa0efffb64e5d058e61c5aa682.tar.gz go-f199f292e72b97aa0efffb64e5d058e61c5aa682.zip |
big: add ModInverse.
ModInverse is just a small wrapper around GcdInt, but it's nice to
have in order to be clear about what one is doing in other code.
R=gri, agl1
CC=golang-dev
https://golang.org/cl/1244045
-rwxr-xr-x | src/pkg/big/int.go | 14 | ||||
-rwxr-xr-x | src/pkg/big/int_test.go | 27 |
2 files changed, 41 insertions, 0 deletions
diff --git a/src/pkg/big/int.go b/src/pkg/big/int.go index a74028fd74..da4e1c83ca 100755 --- a/src/pkg/big/int.go +++ b/src/pkg/big/int.go @@ -518,6 +518,20 @@ func ProbablyPrime(z *Int, n int) bool { } +// ModInverse sets z to the multiplicative inverse of g in the group ℤ/pℤ (where +// p is a prime) and returns z. +func (z *Int) ModInverse(g, p *Int) *Int { + var d Int + GcdInt(&d, z, nil, g, p) + // x and y are such that g*x + p*y = d. Since p is prime, d = 1. Taking + // that modulo p results in g*x = 1, therefore x is the inverse element. + if z.neg { + z.Add(z, p) + } + return z +} + + // Lsh sets z = x << n and returns z. func (z *Int) Lsh(x *Int, n uint) *Int { z.abs = z.abs.shl(x.abs, n) diff --git a/src/pkg/big/int_test.go b/src/pkg/big/int_test.go index e92ebe508a..269c814d46 100755 --- a/src/pkg/big/int_test.go +++ b/src/pkg/big/int_test.go @@ -1019,3 +1019,30 @@ func TestNot(t *testing.T) { } } } + + +type modInverseTest struct { + element string + prime string +} + +var modInverseTests = []modInverseTest{ + modInverseTest{"1", "7"}, + modInverseTest{"1", "13"}, + modInverseTest{"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"}, +} + +func TestModInverse(t *testing.T) { + var element, prime Int + one := NewInt(1) + for i, test := range modInverseTests { + (&element).SetString(test.element, 10) + (&prime).SetString(test.prime, 10) + inverse := new(Int).ModInverse(&element, &prime) + inverse.Mul(inverse, &element) + inverse.Mod(inverse, &prime) + if inverse.Cmp(one) != 0 { + t.Errorf("#%d: failed (e·e^(-1)=%s)", i, inverse) + } + } +} |