From 4d9b0b7cb5c749cd1db3828ab9a3475e6c9811b6 Mon Sep 17 00:00:00 2001
From: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sat, 21 Dec 2024 14:50:33 +0100
Subject: simlified extended gcd

---
 zmodn.h | 22 +++-------------------
 1 file changed, 3 insertions(+), 19 deletions(-)

diff --git a/zmodn.h b/zmodn.h
index 8981257..562aa22 100644
--- a/zmodn.h
+++ b/zmodn.h
@@ -46,26 +46,10 @@ private:
 	int64_t int64;
 };
 
-void swapdiv(int64_t& oldx, int64_t& x, int64_t q) {
-	int64_t tmp = x;
-	x = oldx - q*tmp;
-	oldx = tmp;
-}
-
 std::tuple<int64_t, int64_t, int64_t> extended_gcd(int64_t a, int64_t b) {
-	int64_t oldr = a;
-	int64_t r = b;
-	int64_t olds = 1;
-	int64_t s = 0;
-	int64_t oldt = 0;
-	int64_t t = 1;
-	while (r != 0) {
-		auto q = oldr / r;
-		swapdiv(oldr, r, q);
-		swapdiv(olds, s, q);
-		swapdiv(oldt, t, q);
-	}
-	return {oldr, olds, oldt};
+	if (b == 0) return {a, 1, 0};
+	auto [g, x, y] = extended_gcd(b, a%b);
+	return {g, y, x - y*(a/b)};
 }
 
 #endif
-- 
cgit v1.2.3