Support a negative base in power_mod

Closes #1168

1 files changed, 16 insertions, 3 deletions

diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 4e8a5d8cc..27fb73d08 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -379,9 +379,22 @@ BigInt power_mod(const BigInt& base, const BigInt& exp, const BigInt& mod)
    * minimal window. This makes sense given that here we know that any
    * precomputation is wasted.
    */
-   pow_mod.set_base(base);
-   pow_mod.set_exponent(exp);
-   return pow_mod.execute();
+
+   if(base.is_negative())
+      {
+      pow_mod.set_base(-base);
+      pow_mod.set_exponent(exp);
+      if(exp.is_even())
+         return pow_mod.execute();
+      else
+         return (mod - pow_mod.execute());
+      }
+   else
+      {
+      pow_mod.set_base(base);
+      pow_mod.set_exponent(exp);
+      return pow_mod.execute();
+      }
    }
 
 namespace {