Add tests and timings for inverse_mod

5 files changed, 103 insertions, 14 deletions

diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index b643bd605..45a0b4717 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -190,13 +190,21 @@ std::string Timer::result_string_ops(const Timer& timer)
 
    const double events_per_second = timer.events() / timer.seconds();
 
-   oss << timer.get_name() << " "
-       << static_cast<uint64_t>(events_per_second)
-       << ' ' << timer.doing() << "/sec; "
-       << std::setprecision(2) << std::fixed
-       << timer.ms_per_event() << " ms/op"
-       << " (" << timer.events() << " " << (timer.events() == 1 ? "op" : "ops")
-       << " in " << timer.milliseconds() << " ms)\n";
+   oss << timer.get_name() << " ";
+
+   if(timer.events() == 0)
+      {
+      oss << "no events\n";
+      }
+   else
+      {
+      oss << static_cast<uint64_t>(events_per_second)
+          << ' ' << timer.doing() << "/sec; "
+          << std::setprecision(2) << std::fixed
+          << timer.ms_per_event() << " ms/op"
+          << " (" << timer.events() << " " << (timer.events() == 1 ? "op" : "ops")
+          << " in " << timer.milliseconds() << " ms)\n";
+      }
 
    return oss.str();
    }
@@ -360,6 +368,10 @@ class Speed final : public Command
                {
                bench_random_prime(msec);
                }
+            else if(algo == "inverse_mod")
+               {
+               bench_inverse_mod(msec);
+               }
 #endif
             else if(algo == "RNG")
                {
@@ -601,6 +613,25 @@ class Speed final : public Command
          }
 
 #if defined(BOTAN_HAS_NUMBERTHEORY)
+
+      void bench_inverse_mod(const std::chrono::milliseconds runtime)
+         {
+         const Botan::BigInt p = random_prime(rng(), 1024);
+
+         Timer invmod_timer("inverse_mod");
+
+         while(invmod_timer.under(runtime))
+            {
+            const Botan::BigInt x(rng(), 1023);
+
+            const Botan::BigInt x_inv1 = invmod_timer.run([&]{
+               return Botan::inverse_mod(x, p);
+               });
+            }
+
+         output() << Timer::result_string_ops(invmod_timer);
+         }
+
       void bench_random_prime(const std::chrono::milliseconds runtime)
          {
          const size_t coprime = 65537; // simulates RSA key gen
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
diff --git a/src/tests/data/bn/invmod.vec b/src/tests/data/bn/invmod.vec
new file mode 100644
index 000000000..f97049583
--- /dev/null
+++ b/src/tests/data/bn/invmod.vec
@@ -0,0 +1,21 @@
+
+Input = 10
+Modulus = 37
+Output = 26
+
+Input = 5
+Modulus = 0x7fffffffffffffffffffffffffffffff
+Output = 0x33333333333333333333333333333333
+
+Input = 333
+Modulus = 0x7fffffffffffffffffffffffffffffff
+Output = 0x17d4f2ee517d4f2ee517d4f2ee517d4f
+
+Input = 0x435b21e35ccd62dbdbafa1368cf742f0
+Modulus = 0x7fffffffffffffffffffffffffffffff
+Output = 0x604ddb74e5a55e559a7320e45b06eaf6
+
+Input = 2
+Modulus = 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+Output  = 0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
+
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index 9e3412ada..671c76bff 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -392,7 +392,7 @@ class BigInt_IsPrime_Test : public Text_Based_Test
          const BigInt value = get_req_bn(vars, "Value");
          const bool v_is_prime = get_req_sz(vars, "IsPrime") > 0;
 
-         result.test_eq("value", Botan::is_prime(value, Test::rng()), v_is_prime);
+         result.test_eq("is_prime", Botan::is_prime(value, Test::rng()), v_is_prime);
 
          return result;
          }
@@ -415,7 +415,7 @@ class BigInt_Ressol_Test : public Text_Based_Test
 
          const Botan::BigInt a_sqrt = Botan::ressol(a, p);
 
-         result.test_eq("result", a_sqrt, exp);
+         result.test_eq("ressol", a_sqrt, exp);
 
          if(a_sqrt > 1)
             {
@@ -429,6 +429,35 @@ class BigInt_Ressol_Test : public Text_Based_Test
 
 BOTAN_REGISTER_TEST("bn_ressol", BigInt_Ressol_Test);
 
+class BigInt_InvMod_Test : public Text_Based_Test
+   {
+   public:
+      BigInt_InvMod_Test() : Text_Based_Test("bn/invmod.vec", {"Input","Modulus","Output"}) {}
+
+      Test::Result run_one_test(const std::string&, const VarMap& vars) override
+         {
+         Test::Result result("BigInt InvMod");
+
+         const Botan::BigInt a = get_req_bn(vars, "Input");
+         const Botan::BigInt mod = get_req_bn(vars, "Modulus");
+         const Botan::BigInt expected = get_req_bn(vars, "Output");
+
+         const Botan::BigInt a_inv = Botan::inverse_mod(a, mod);
+
+         result.test_eq("inverse_mod", a_inv, expected);
+
+         if(a_inv > 1)
+            {
+            const Botan::BigInt z = (a * a_inv) % mod;
+            result.test_eq("inverse ok", z, 1);
+            }
+
+         return result;
+         }
+   };
+
+BOTAN_REGISTER_TEST("bn_invmod", BigInt_InvMod_Test);
+
 #endif
 
 }