From 771667c2bb52235d6dacf67eab933207b59e167b Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sat, 21 Dec 2024 17:54:02 +0100 Subject: Fix division --- test | 10 ++++++++++ zmodn.h | 8 +++++--- 2 files changed, 15 insertions(+), 3 deletions(-) diff --git a/test b/test index 4b426c2..d80dc2b 100755 --- 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 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