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