Support a negative base in power_mod

Closes #1168

3 files changed, 44 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 {
diff --git a/src/tests/data/bn/powmod.vec b/src/tests/data/bn/powmod.vec
index 024a2d36b..2165ed52c 100644
--- a/src/tests/data/bn/powmod.vec
+++ b/src/tests/data/bn/powmod.vec
@@ -216,3 +216,25 @@ Exponent = 0x2000000000000000000000000000000000000000000000000000000000060800000
 Modulus  = 0x40000000000000000000000000000000000000000000000000000000000c100000000000000fffd
 Output = 0x9943fa648c48cb4cd01756bed11e3382aca74d84fb0bf8cf8d56cd4524f80538d4888cbd23b8e2
 
+# Check support for negative base (GH #1168)
+
+Base = -5
+Exponent = 10
+Modulus = 37
+Output = 30
+
+Base = -5
+Exponent = 11
+Modulus = 37
+Output = 35
+
+Base = -0xFFE0000FFF80003F00000000FF
+Exponent = 0x7FF7C00200
+Modulus = 0xFFFFFFC00000000000003FFFFF
+Output = 0xCAEB2FF794C6783C4F1F06E684
+
+Base = -0xF9FFFFF000000FFFFFFFFFFFFFFFC0000000
+Exponent = 0x83FFFF000000000000000003FFFFFFFFFFFF
+Modulus = 0xFFE007FFF9F83FFFFF8F000FFFFFFFFFFFFF
+Output = 7559902530247723476756105022122181875899018
+
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index 0dc07aabf..61be15d15 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -492,6 +492,12 @@ class BigInt_Powmod_Test : public Text_Based_Test
 
          result.test_eq("power_mod", Botan::power_mod(base, exponent, modulus), expected);
 
+         /*
+         * Only the basic power_mod interface supports negative base
+         */
+         if(base.is_negative())
+            return result;
+
          Botan::Power_Mod pow_mod1(modulus);
 
          pow_mod1.set_base(base);