From c8bfbfb85e368511a033561cd68f7e86f14fcde7 Mon Sep 17 00:00:00 2001 From: siddharth ravikumar Date: Thu, 11 Aug 2022 19:34:11 -0400 Subject: lib: add egcd --- lib/rsa.go | 65 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 65 insertions(+) create mode 100644 lib/rsa.go (limited to 'lib/rsa.go') diff --git a/lib/rsa.go b/lib/rsa.go new file mode 100644 index 0000000..86df861 --- /dev/null +++ b/lib/rsa.go @@ -0,0 +1,65 @@ +// Copyright © 2021 siddharth ravikumar +// SPDX-License-Identifier: ISC + +package lib + +import ( + "math/big" +) + +type GCDResult struct { + Gcd *big.Int + X *big.Int // Bézout coefficient 'x' + Y *big.Int // Bézout coefficient 'y' +} + +// Copy b to a. +func biCopy(a, b *big.Int) *big.Int { + a.SetBytes(b.Bytes()) + if b.Sign() == -1 { + a.Mul(a, big.NewInt(-1)) + } + return a +} + +// Extended Euclidian. +func egcd(a, b *big.Int) GCDResult { + // Initialize. + s0 := big.NewInt(1) + s1 := big.NewInt(0) + r0 := biCopy(big.NewInt(0), a) + r1 := biCopy(big.NewInt(0), b) + + for r1.Cmp(big.NewInt(0)) != 0 { + q := big.NewInt(0) + q.Div(r0, r1) + + tr := big.NewInt(0) + tr = tr.Mul(q, r1) + tr = tr.Sub(r0, tr) + + biCopy(r0, r1) + biCopy(r1, tr) + + tr = big.NewInt(0) + tr = tr.Mul(q, s1) + tr = tr.Sub(s0, tr) + + biCopy(s0, s1) + biCopy(s1, tr) + } + + x := biCopy(big.NewInt(0), s0) + y := big.NewInt(0) + if b.Cmp(big.NewInt(0)) != 0 { + y = y.Mul(s0, a) + y = y.Sub(r0, y) + y = y.Div(y, b) + } + + return GCDResult{ + Gcd: biCopy(big.NewInt(0), r0), + X: x, + Y: y, + } +} -- cgit v1.2.3