From 771667c2bb52235d6dacf67eab933207b59e167b Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sat, 21 Dec 2024 17:54:02 +0100 Subject: Fix division --- zmodn.h | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) (limited to 'zmodn.h') diff --git a/zmodn.h b/zmodn.h index fdb1ee6..890fb0e 100644 --- a/zmodn.h +++ b/zmodn.h @@ -40,13 +40,15 @@ public: bool operator!=(const Zmod& z) const { return value != z.value; } std::optional inverse() const { - auto [g, a, _] = extended_gcd(value, N); + auto [g, a, b] = extended_gcd(value, N); return g == 1 ? Zmod(a) : std::optional{}; } std::optional 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{value / g, d.toint() / g}; + auto i = b.inverse(); + return i ? a * i.value() : i; } std::optional operator/=(const Zmod& d) { -- cgit v1.2.3