Add tests and timings for inverse_mod

2 files changed, 13 insertions, 5 deletions

diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 31dd72feb..982e9264a 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -74,8 +74,6 @@ BigInt lcm(const BigInt& a, const BigInt& b)
    return ((a * b) / gcd(a, b));
    }
 
-namespace {
-
 /*
 * If the modulus is odd, then we can avoid computing A and C. This is
 * a critical path algorithm in some instances and an odd modulus is
@@ -84,6 +82,11 @@ namespace {
 */
 BigInt inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod)
    {
+   if(n.is_negative() || mod.is_negative())
+      throw Invalid_Argument("inverse_mod_odd_modulus: arguments must be non-negative");
+   if(mod < 3 || mod.is_even())
+      throw Invalid_Argument("Bad modulus to inverse_mod_odd_modulus");
+
    BigInt u = mod, v = n;
    BigInt B = 0, D = 1;
 
@@ -120,8 +123,6 @@ BigInt inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod)
    return D;
    }
 
-}
-
 /*
 * Find the Modular Inverse
 */
diff --git a/src/lib/math/numbertheory/numthry.h b/src/lib/math/numbertheory/numthry.h
index 5df0858ee..b9a082c6c 100644
--- a/src/lib/math/numbertheory/numthry.h
+++ b/src/lib/math/numbertheory/numthry.h
@@ -69,12 +69,19 @@ BigInt BOTAN_DLL square(const BigInt& x);
 * Modular inversion
 * @param x a positive integer
 * @param modulus a positive integer
-* @return y st (x*y) % modulus == 1
+* @return y st (x*y) % modulus == 1 or 0 if no such value
 */
 BigInt BOTAN_DLL inverse_mod(const BigInt& x,
                              const BigInt& modulus);
 
 /**
+* As above but requires modulus be odd
+*/
+BigInt BOTAN_DLL inverse_mod_odd_modulus(const BigInt& x,
+                                         const BigInt& modulus);
+
+
+/**
 * Compute the Jacobi symbol. If n is prime, this is equivalent
 * to the Legendre symbol.
 * @see http://mathworld.wolfram.com/JacobiSymbol.html