lib: add egcd

2 files changed, 117 insertions, 0 deletions

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 <s@ricketyspace.net>
+// 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,
+	}
+}
diff --git a/lib/rsa_test.go b/lib/rsa_test.go
new file mode 100644
index 0000000..ee71755
--- /dev/null
+++ b/lib/rsa_test.go
@@ -0,0 +1,52 @@
+// Copyright © 2021 siddharth ravikumar <s@ricketyspace.net>
+// SPDX-License-Identifier: ISC
+
+package lib
+
+import (
+	"math/big"
+	"testing"
+)
+
+func TestEGCD(t *testing.T) {
+	a := big.NewInt(128)
+	b := big.NewInt(96)
+	r := egcd(a, b)
+	if r.Gcd.Cmp(big.NewInt(32)) != 0 {
+		t.Errorf("gcd(128, 96) != 32")
+	}
+	if r.X.Cmp(big.NewInt(1)) != 0 || r.Y.Cmp(big.NewInt(-1)) != 0 {
+		t.Errorf("bézout_coef(128, 96) != {1,-1}")
+	}
+
+	a = big.NewInt(360)
+	b = big.NewInt(210)
+	r = egcd(a, b)
+	if r.Gcd.Cmp(big.NewInt(30)) != 0 {
+		t.Errorf("gcd(360, 210) != 30")
+	}
+	if r.X.Cmp(big.NewInt(3)) != 0 || r.Y.Cmp(big.NewInt(-5)) != 0 {
+		t.Errorf("bézout_coef(360, 210) != {3,-5}")
+	}
+
+	a = big.NewInt(108)
+	b = big.NewInt(144)
+	r = egcd(a, b)
+	if r.Gcd.Cmp(big.NewInt(36)) != 0 {
+		t.Errorf("gcd(108, 144) != 36")
+	}
+	if r.X.Cmp(big.NewInt(-1)) != 0 || r.Y.Cmp(big.NewInt(1)) != 0 {
+		t.Errorf("bézout_coef(108, 144) != {-1,1}")
+	}
+
+	a = big.NewInt(240)
+	b = big.NewInt(46)
+	r = egcd(a, b)
+	if r.Gcd.Cmp(big.NewInt(2)) != 0 {
+		t.Errorf("gcd(240, 46) != 2")
+	}
+	if r.X.Cmp(big.NewInt(-9)) != 0 || r.Y.Cmp(big.NewInt(47)) != 0 {
+		t.Errorf("bézout_coef(240, 46) != {-9,47}")
+	}
+
+}