1 /*
2 * (C) 2009-2010 Jack Lloyd
3 *
4 * Distributed under the terms of the Botan license
5 *
6 * Factor integers using a combination of trial division by small
7 * primes, and Pollard's Rho algorithm
8 */
9
10 #include <botan/botan.h>
11 #include <botan/reducer.h>
12 #include <botan/numthry.h>
13 using namespace Botan;
14
15 #include <algorithm>
16 #include <iostream>
17 #include <iterator>
18
19 namespace {
20
21 /*
22 * Pollard's Rho algorithm, as described in the MIT algorithms book. We
23 * use (x^2+x) mod n instead of (x*2-1) mod n as the random function,
24 * it _seems_ to lead to faster factorization for the values I tried.
25 */
rho(const BigInt & n,RandomNumberGenerator & rng)26 BigInt rho(const BigInt& n, RandomNumberGenerator& rng)
27 {
28 BigInt x = BigInt::random_integer(rng, 0, n-1);
29 BigInt y = x;
30 BigInt d = 0;
31
32 Modular_Reducer mod_n(n);
33
34 u32bit i = 1, k = 2;
35 while(true)
36 {
37 i++;
38
39 if(i == 0) // overflow, bail out
40 break;
41
42 x = mod_n.multiply((x + 1), x);
43
44 d = gcd(y - x, n);
45 if(d != 1 && d != n)
46 return d;
47
48 if(i == k)
49 {
50 y = x;
51 k = 2*k;
52 }
53 }
54 return 0;
55 }
56
57 // Remove (and return) any small (< 2^16) factors
remove_small_factors(BigInt & n)58 std::vector<BigInt> remove_small_factors(BigInt& n)
59 {
60 std::vector<BigInt> factors;
61
62 while(n.is_even())
63 {
64 factors.push_back(2);
65 n /= 2;
66 }
67
68 for(u32bit j = 0; j != PRIME_TABLE_SIZE; j++)
69 {
70 if(n < PRIMES[j])
71 break;
72
73 BigInt x = gcd(n, PRIMES[j]);
74
75 if(x != 1)
76 {
77 n /= x;
78
79 u32bit occurs = 0;
80 while(x != 1)
81 {
82 x /= PRIMES[j];
83 occurs++;
84 }
85
86 for(u32bit k = 0; k != occurs; k++)
87 factors.push_back(PRIMES[j]);
88 }
89 }
90
91 return factors;
92 }
93
factorize(const BigInt & n_in,RandomNumberGenerator & rng)94 std::vector<BigInt> factorize(const BigInt& n_in,
95 RandomNumberGenerator& rng)
96 {
97 BigInt n = n_in;
98 std::vector<BigInt> factors = remove_small_factors(n);
99
100 while(n != 1)
101 {
102 if(check_prime(n, rng))
103 {
104 factors.push_back(n);
105 break;
106 }
107
108 BigInt a_factor = 0;
109 while(a_factor == 0)
110 a_factor = rho(n, rng);
111
112 std::vector<BigInt> rho_factored = factorize(a_factor, rng);
113 for(u32bit j = 0; j != rho_factored.size(); j++)
114 factors.push_back(rho_factored[j]);
115
116 n /= a_factor;
117 }
118 return factors;
119 }
120
121 }
122
main(int argc,char * argv[])123 int main(int argc, char* argv[])
124 {
125 if(argc != 2)
126 {
127 std::cerr << "Usage: " << argv[0] << " integer\n";
128 return 1;
129 }
130
131 Botan::LibraryInitializer init;
132
133 try
134 {
135 BigInt n(argv[1]);
136
137 AutoSeeded_RNG rng;
138
139 std::vector<BigInt> factors = factorize(n, rng);
140 std::sort(factors.begin(), factors.end());
141
142 std::cout << n << ": ";
143 std::copy(factors.begin(),
144 factors.end(),
145 std::ostream_iterator<BigInt>(std::cout, " "));
146 std::cout << "\n";
147 }
148 catch(std::exception& e)
149 {
150 std::cout << e.what() << std::endl;
151 return 1;
152 }
153 return 0;
154 }
155