diff options
Diffstat (limited to 'src/lib')
-rw-r--r-- | src/lib/math/numbertheory/numthry.cpp | 9 | ||||
-rw-r--r-- | src/lib/math/numbertheory/numthry.h | 9 |
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 |