diff options
| -rw-r--r-- | src/cli/speed.cpp | 45 | ||||
| -rw-r--r-- | src/lib/math/numbertheory/numthry.cpp | 9 | ||||
| -rw-r--r-- | src/lib/math/numbertheory/numthry.h | 9 | ||||
| -rw-r--r-- | src/tests/data/bn/invmod.vec | 21 | ||||
| -rw-r--r-- | src/tests/test_bigint.cpp | 33 |
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 } |