zmodn

commit 771667c2bb52235d6dacf67eab933207b59e167b
parent 32cce8fe6a4b35d24d6a63b3226daee2a2753684
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Sat, 21 Dec 2024 17:54:02 +0100

Fix division

Diffstat:
M
test
 | 
10
++++++++++
M
zmodn.h
 | 
8
+++++---

2 files changed, 15 insertions(+), 3 deletions(-)
diff --git a/test b/test
@@ -141,6 +141,16 @@ public:
 		assert_equal(p, 92);
 	}
 },
+{
+	.name = "4 / 2 mod 6",
+	.f = []() {
+		Zmod<6> four = 4;
+		Zmod<6> two = 2;
+		auto d = four / two;
+		assert_equal(d.has_value(), true);
+		assert_equal(d.value(), 2);
+	}
+},
 };
 
 int main() {
diff --git a/zmodn.h b/zmodn.h
@@ -40,13 +40,15 @@ public:
 	bool operator!=(const Zmod& z) const { return value != z.value; }
 
 	std::optional<Zmod> inverse() const {
-		auto [g, a, _] = extended_gcd(value, N);
+		auto [g, a, b] = extended_gcd(value, N);
 		return g == 1 ? Zmod(a) : std::optional<Zmod>{};
 	}
 
 	std::optional<Zmod> operator/(const Zmod& d) const {
-		auto i = d.inverse();
-		return i ? (*this) * i.value() : i;
+		auto [g, x, y] = extended_gcd(value, d.toint());
+		auto [a, b] = std::pair<Zmod, Zmod>{value / g, d.toint() / g};
+		auto i = b.inverse();
+		return i ? a * i.value() : i;
 	}
 
 	std::optional<Zmod> operator/=(const Zmod& d) {