This article is part of a set of articles. Each article highlights an aspect around Integer Factorization.
When starting to play with Integer Factorization, trying all possible factors is the first idea, that algorithm is named Trial Division.
The algorithm has two purposes - finding a prime factor or finding if an integer is a prime by not by finding a prime factor.
Since the algorithm is about finding a factor, the worst case is when the integer to factorize is a prime.
It looks obvious that the most efficient method is to check only prime numbers, but handling the list of primes is a problem by itself. The classical variants exist as solutions to avoid that problem. As methods get more sophisticated, they remove more useless non prime numbers, thus being more efficient.
Some newbies are testing every single number below n. That's overkill. The inefficiency remains hidden as long the integer to factorize is not a prime.
The maximum cost for n is n-2 divisions. Complexity of O(n) is n.
Testing all numbers until n/2 is better, but is also overkill. Just like with the previous method, the inefficiency remains hidden as long the integer to factorize is not a prime.
The maximum cost for n is n / 2 divisions. Complexity of O(n) is n / 2.
A little analysis shows that there is no factor to check after the square root.
The maximum cost for n is √n divisions. Complexity of O(n) is √n.
With further analysis, one can see that there is no even factor beyond 2.
The maximum cost for n is (√n) * 1 / 2 => (√n) * 0.50 divisions. Complexity of O(n) is √n.
The wheel is an extension of the previous optimization. One builds the wheel from small primes, say 2 and 3, the size of the wheel is 2 * 3 = 6. When one writes a list of numbers in a 6 columns table and removes 2 and 3, one can see that primes are only in the first column and in the fifth column. That is the wheel, we only have to check numbers of columns 1 and 5.
The maximum cost for n is (√n) * (1 / 2) * (2 / 3) => (√n) * (1 / 3) => (√n) * 0.33 divisions. Complexity of O(n) is √n.
The wheel can include more primes. With 2, 3 and 5, the size of wheel is 30.
The maximum cost for n is (√n) * (1 / 2) * (2 / 3) * (4 / 5) => (√n) * (4 / 15) => (√n) * 0.27 divisions. Complexity of O(n) is √n.
Or get even bigger. With 2, 3, 5 and 7, the size of wheel is 210.
The maximum cost for n is (√n) * (1 / 2) * (2 / 3) * (4 / 5) * (6 / 7) => (√n) * (24 / 105) => (√n) * 0.23 divisions. Complexity of O(n) is √n.
Basically, it is a wheel variant, where the list of small primes exceeds the ones needed for the wheel, and after the end of list, we fall back on the wheel. The advantage over the simple wheel is that it avoids testing non prime factors not filtered by the wheel. As long as we are in the list of primes, the workload is optimum.
Just have to take care about setting the wheel correctly at the end of prime list.
The maximum cost for n is slightly better than the wheel, the list primes just save non prime divisors that are in the wheel. So the longer the list of primes, the better it gets. Complexity of O(n) is √n.
long long TD_SRPW(long long Cand) {
long long SPrimes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191,
193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347,
349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421,
431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593,
599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661,
673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757,
761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853,
857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021,
1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093,
1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181,
1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259,
1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321,
1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433,
1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579,
1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657,
1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741,
1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831,
1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913,
1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003,
2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087,
2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269,
2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347,
2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417,
2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,
2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621,
2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693,
2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767,
2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851,
2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953,
2957, 2963, 2969, 2971, 2999, 0 };
long long Wheel[] = { 6, 4, 2, 4, 2, 4, 6, 2, 0 };
long long Div;
Count = 0;
long long Top = sqrt(Cand);
for (long long Ind = 0; SPrimes[Ind] != 0; Ind++) {
Div = SPrimes[Ind]; if (SPrimes[Ind] > Top) {
return Cand;
}
Count++;
if (Cand % SPrimes[Ind] == 0) {
return SPrimes[Ind];
}
}
Div = 3001;
while (Div <= Top) {
for (long long Ind = 0; Wheel[Ind] != 0; Ind++) {
if (Div > Top) {
return Cand;
}
Count++;
if (Cand % Div == 0) {
return Div;
}
Div += Wheel[Ind];
}
}
return Cand;
}
function TD_SRW2(Prod)
local D, Top, SPrimes, Wheel, W
SPrimes= {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139,
149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293}
Wheel= {6, 4, 2, 4, 2, 4, 6, 2}
for each D in SPrimes
if Prod % D = 0
return D
endif
next
D= 301
Top= int(sqrt(Prod))
while D <= Top
for each W in wheel
D += W
if Prod % D = 0
return D
endif
next
enddo
return Prod
Benchmarks are here to highlight efficiency of variants.
As divisions/modulos are what cost time, counting them is enough for the benchmark.
This first benchmark is here to highlight the inefficiency of Brute Force variant.
This extended benchmark is for variants other than Brute Force.
Delta shows how the list of primes improves things, and it gets better with long list of primes.
Rgis code checks correctness of code by comparing results of variants.
Trial Division being brute force, one can see that there is brute force and brute force.