From e12ccae7a96c01dce5e86aa17c27e20644c75a15 Mon Sep 17 00:00:00 2001 From: siddharth ravikumar Date: Thu, 11 Aug 2022 20:30:53 -0400 Subject: lib: add invmod --- lib/rsa.go | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) (limited to 'lib/rsa.go') diff --git a/lib/rsa.go b/lib/rsa.go index 86df861..2c0769b 100644 --- a/lib/rsa.go +++ b/lib/rsa.go @@ -63,3 +63,38 @@ func egcd(a, b *big.Int) GCDResult { Y: y, } } + +func invmod(a, n *big.Int) (*big.Int, error) { + // Initialize. + t0 := big.NewInt(0) + t1 := big.NewInt(1) + r0 := biCopy(big.NewInt(0), n) + r1 := biCopy(big.NewInt(0), a) + + for r1.Cmp(big.NewInt(0)) != 0 { + q := big.NewInt(0) + q.Div(r0, r1) + + tt := big.NewInt(0) + tt = tt.Mul(q, t1) + tt = tt.Sub(t0, tt) + + biCopy(t0, t1) + biCopy(t1, tt) + + tr := big.NewInt(0) + tr = tr.Mul(q, r1) + tr = tr.Sub(r0, tr) + + biCopy(r0, r1) + biCopy(r1, tr) + } + + if r0.Cmp(big.NewInt(1)) > 0 { + return nil, CPError{"not invertible"} + } + if t0.Cmp(big.NewInt(0)) < 0 { + t0.Add(t0, n) + } + return t0, nil +} -- cgit v1.2.3