aboutsummaryrefslogtreecommitdiffstats
path: root/doc/examples
diff options
context:
space:
mode:
authorlloyd <[email protected]>2006-07-16 08:18:29 +0000
committerlloyd <[email protected]>2006-07-16 08:18:29 +0000
commitf731d5aa28ca07472f10e886615e43ce06f8656d (patch)
treeb72d9c8132d4b193b8663e5800d6f61e774c2976 /doc/examples
parentf2c092544d0144bde0880931772ee87c02f47ae1 (diff)
Add an example that performs factoring (using Pollard's Rho algorithm)
Diffstat (limited to 'doc/examples')
-rw-r--r--doc/examples/Makefile6
-rw-r--r--doc/examples/factor.cpp110
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;
+ }