From b046a916a4f3a79d69fb01e45e05ed51ce3e9dcd Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Sat, 2 Sep 2017 05:38:05 -0400 Subject: Support a negative base in power_mod Closes #1168 --- src/lib/math/numbertheory/numthry.cpp | 19 ++++++++++++++++--- 1 file changed, 16 insertions(+), 3 deletions(-) (limited to 'src/lib/math') 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 { -- cgit v1.2.3