From 8ca27427af98bd3a82e8c5f4a199513295747930 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sat, 21 Dec 2024 18:13:27 +0100 Subject: Revert "Fix division" Actually you cannot do division like that, the result is not unique. This reverts commit 771667c2bb52235d6dacf67eab933207b59e167b. --- zmodn.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'zmodn.h') diff --git a/zmodn.h b/zmodn.h index 890fb0e..fdb1ee6 100644 --- a/zmodn.h +++ b/zmodn.h @@ -40,15 +40,13 @@ public: bool operator!=(const Zmod& z) const { return value != z.value; } std::optional inverse() const { - auto [g, a, b] = extended_gcd(value, N); + auto [g, a, _] = extended_gcd(value, N); return g == 1 ? Zmod(a) : std::optional{}; } std::optional operator/(const Zmod& d) const { - 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; + auto i = d.inverse(); + return i ? (*this) * i.value() : i; } std::optional operator/=(const Zmod& d) { -- cgit v1.3