diff options
author | lloyd <[email protected]> | 2006-07-16 08:18:29 +0000 |
---|---|---|
committer | lloyd <[email protected]> | 2006-07-16 08:18:29 +0000 |
commit | f731d5aa28ca07472f10e886615e43ce06f8656d (patch) | |
tree | b72d9c8132d4b193b8663e5800d6f61e774c2976 /doc/examples | |
parent | f2c092544d0144bde0880931772ee87c02f47ae1 (diff) |
Add an example that performs factoring (using Pollard's Rho algorithm)
Diffstat (limited to 'doc/examples')
-rw-r--r-- | doc/examples/Makefile | 6 | ||||
-rw-r--r-- | doc/examples/factor.cpp | 110 |
2 files changed, 115 insertions, 1 deletions
diff --git a/doc/examples/Makefile b/doc/examples/Makefile index 351d802da..f87811d3f 100644 --- a/doc/examples/Makefile +++ b/doc/examples/Makefile @@ -16,7 +16,7 @@ RSA_EX = rsa_kgen rsa_enc rsa_dec DSA_EX = dsa_kgen dsa_sign dsa_ver DH_EX = dh HASH_EX = hash hash_fd hasher hasher2 stack -MISC_EX = base base64 bzip encrypt decrypt fips140 xor_ciph +MISC_EX = factor base base64 bzip encrypt decrypt fips140 xor_ciph PROGS = $(X509_EX) $(RSA_EX) $(DSA_EX) $(DH_EX) $(HASH_EX) $(MISC_EX) @@ -75,6 +75,10 @@ fips140: fips140.cpp $(CXX) $(FLAGS) $? $(LIBS) -o $@ @$(STRIP) $@ +factor: factor.cpp + $(CXX) $(FLAGS) $? $(LIBS) -o $@ + @$(STRIP) $@ + hash: hash.cpp $(CXX) $(FLAGS) $? $(LIBS) -o $@ @$(STRIP) $@ diff --git a/doc/examples/factor.cpp b/doc/examples/factor.cpp new file mode 100644 index 000000000..f7b085b86 --- /dev/null +++ b/doc/examples/factor.cpp @@ -0,0 +1,110 @@ +/* + Factor integers using a combination of trial division by small primes, + and Pollard's Rho algorithm +*/ +#include <botan/botan.h> +#include <botan/reducer.h> +#include <botan/numthry.h> +using namespace Botan; + +#include <iostream> + +BigInt rho(const BigInt& n) + { + BigInt x = random_integer(0, n-1); + BigInt y = x; + BigInt d = 0; + + Modular_Reducer mod_n(n); + + u32bit i = 1, k = 2; + while(true) + { + i++; + + if(i == 0) // fail + break; + + x = mod_n.reduce(square(x) - 1); + d = gcd(y - x, n); + if(d != 1 && d != n) + return d; + + if(i == k) + { + y = x; + k = 2*k; + } + } + return 0; + } + +void concat(std::vector<BigInt>& x, const std::vector<BigInt>& y) + { + for(u32bit j = 0; j != y.size(); j++) + x.push_back(y[j]); + } + +std::vector<BigInt> factorize(const BigInt& n) + { + std::vector<BigInt> factors; + + if(n <= 1) // no prime factors at all + return factors; + + if(is_prime(n)) // just n itself + { + factors.push_back(n); + return factors; + } + + if(n.is_even()) + { + factors.push_back(2); + concat(factors, factorize(n / 2)); + return factors; + } + + BigInt factor = 0; + while(factor == 0) + { + std::cout << "Trying to factorize " << n << "\n"; + factor = rho(n); + } + + concat(factors, factorize(factor)); + concat(factors, factorize(n / factor)); + + return factors; + } + + +int main(int argc, char* argv[]) + { + if(argc != 2) + { + std::cerr << "Usage: " << argv[0] << " integer\n"; + return 1; + } + + try + { + LibraryInitializer init; + + BigInt n(argv[1]); + std::vector<BigInt> factors = factorize(n); + + std::cout << n << " = "; + for(u32bit j = 0; j != factors.size(); j++) + std::cout << factors[j] << " "; + std::cout << "\n"; + + + } + catch(std::exception& e) + { + std::cout << e.what() << std::endl; + return 1; + } + return 0; + } |