diff options
Diffstat (limited to 'comm/third_party/botan/src/cli/math.cpp')
| -rw-r--r-- | comm/third_party/botan/src/cli/math.cpp | 269 |
1 files changed, 269 insertions, 0 deletions
diff --git a/comm/third_party/botan/src/cli/math.cpp b/comm/third_party/botan/src/cli/math.cpp new file mode 100644 index 0000000000..1268cd3e53 --- /dev/null +++ b/comm/third_party/botan/src/cli/math.cpp @@ -0,0 +1,269 @@ +/* +* (C) 2009,2010,2015 Jack Lloyd +* +* Botan is released under the Simplified BSD License (see license.txt) +*/ + +#include "cli.h" + +#if defined(BOTAN_HAS_NUMBERTHEORY) + +#include <botan/numthry.h> +#include <botan/monty.h> +#include <iterator> + +namespace Botan_CLI { + +class Modular_Inverse final : public Command + { + public: + Modular_Inverse() : Command("mod_inverse n mod") {} + + std::string group() const override + { + return "numtheory"; + } + + std::string description() const override + { + return "Calculates a modular inverse"; + } + + void go() override + { + const Botan::BigInt n(get_arg("n")); + const Botan::BigInt mod(get_arg("mod")); + + output() << Botan::inverse_mod(n, mod) << "\n"; + } + }; + +BOTAN_REGISTER_COMMAND("mod_inverse", Modular_Inverse); + +class Gen_Prime final : public Command + { + public: + Gen_Prime() : Command("gen_prime --count=1 bits") {} + + std::string group() const override + { + return "numtheory"; + } + + std::string description() const override + { + return "Samples one or more primes"; + } + + void go() override + { + const size_t bits = get_arg_sz("bits"); + const size_t cnt = get_arg_sz("count"); + + for(size_t i = 0; i != cnt; ++i) + { + const Botan::BigInt p = Botan::random_prime(rng(), bits); + output() << p << "\n"; + } + } + }; + +BOTAN_REGISTER_COMMAND("gen_prime", Gen_Prime); + +class Is_Prime final : public Command + { + public: + Is_Prime() : Command("is_prime --prob=56 n") {} + + std::string group() const override + { + return "numtheory"; + } + + std::string description() const override + { + return "Test if the integer n is composite or prime"; + } + + void go() override + { + Botan::BigInt n(get_arg("n")); + const size_t prob = get_arg_sz("prob"); + const bool prime = Botan::is_prime(n, rng(), prob); + + output() << n << " is " << (prime ? "probably prime" : "composite") << "\n"; + } + }; + +BOTAN_REGISTER_COMMAND("is_prime", Is_Prime); + +/* +* Factor integers using a combination of trial division by small +* primes, and Pollard's Rho algorithm +*/ +class Factor final : public Command + { + public: + Factor() : Command("factor n") {} + + std::string group() const override + { + return "numtheory"; + } + + std::string description() const override + { + return "Factor a given integer"; + } + + void go() override + { + Botan::BigInt n(get_arg("n")); + + std::vector<Botan::BigInt> factors = factorize(n, rng()); + std::sort(factors.begin(), factors.end()); + + output() << n << ": "; + std::copy(factors.begin(), factors.end(), std::ostream_iterator<Botan::BigInt>(output(), " ")); + output() << std::endl; + } + + private: + + std::vector<Botan::BigInt> factorize(const Botan::BigInt& n_in, + Botan::RandomNumberGenerator& rng) + { + Botan::BigInt n = n_in; + std::vector<Botan::BigInt> factors = remove_small_factors(n); + + while(n != 1) + { + if(Botan::is_prime(n, rng)) + { + factors.push_back(n); + break; + } + + Botan::BigInt a_factor = 0; + while(a_factor == 0) + { + a_factor = rho(n, rng); + } + + std::vector<Botan::BigInt> rho_factored = factorize(a_factor, rng); + for(size_t j = 0; j != rho_factored.size(); j++) + { + factors.push_back(rho_factored[j]); + } + + n /= a_factor; + } + + return factors; + } + + /* + * Pollard's Rho algorithm, as described in the MIT algorithms book. + * Uses Brent's cycle finding + */ + Botan::BigInt rho(const Botan::BigInt& n, Botan::RandomNumberGenerator& rng) + { + auto monty_n = std::make_shared<Botan::Montgomery_Params>(n); + + const Botan::Montgomery_Int one(monty_n, monty_n->R1(), false); + + Botan::Montgomery_Int x(monty_n, Botan::BigInt::random_integer(rng, 2, n - 3), false); + Botan::Montgomery_Int y = x; + Botan::Montgomery_Int z = one; + Botan::Montgomery_Int t(monty_n); + Botan::BigInt d; + + Botan::secure_vector<Botan::word> ws; + + size_t i = 1, k = 2; + + while(true) + { + i++; + + if(i >= 0xFFFF0000) // bad seed? too slow? bail out + { + break; + } + + x.square_this(ws); // x = x^2 + x.add(one, ws); + + t = y; + t.sub(x, ws); + + z.mul_by(t, ws); + + if(i == k || i % 128 == 0) + { + d = Botan::gcd(z.value(), n); + z = one; + + if(d == n) + { + // TODO Should rewind here + break; + } + + if(d != 1) + return d; + } + + if(i == k) + { + y = x; + k = 2 * k; + } + } + + // failed + return 0; + } + + // Remove (and return) any small (< 2^16) factors + std::vector<Botan::BigInt> remove_small_factors(Botan::BigInt& n) + { + std::vector<Botan::BigInt> factors; + + while(n.is_even()) + { + factors.push_back(2); + n /= 2; + } + + for(size_t j = 0; j != Botan::PRIME_TABLE_SIZE; j++) + { + uint16_t prime = Botan::PRIMES[j]; + if(n < prime) + { + break; + } + + Botan::BigInt x = Botan::gcd(n, prime); + + if(x != 1) + { + n /= x; + + while(x != 1) + { + x /= prime; + factors.push_back(prime); + } + } + } + + return factors; + } + }; + +BOTAN_REGISTER_COMMAND("factor", Factor); + +} + +#endif |