To factor integers in C you can try to use a probabilistic approach :
The headers of my proposition :
#include <stdlib.h>
#include <sys/time.h>
typedef unsigned long long int positive_number; // __uint128_t
static inline positive_number multiplication_modulo(positive_number lhs, positive_number rhs, positive_number mod);
static int is_prime(positive_number n, int k); // prime checker
positive_number factor_worker(positive_number n);
positive_number factor(positive_number n, int timeout);
The factorization process manager, because there is a timeout:
double microtime() {
struct timeval time; gettimeofday(&time, 0);
return (double) time.tv_sec + (double) time.tv_usec / 1e6;
}
// This is the master function you can call, expecting a number and a timeout(s)
positive_number factor(positive_number n, int timeout) {
if (n < 4) return n;
if (n != (n | 1)) return 2;
double begin = microtime();
int steps = 8; // primality check iterations
positive_number a, b;
for (a = n >> 1, b = (a + n / a) >> 1; b < a; a = b, b = (a + n / a) >> 1, ++steps);
if (b * b == n) return b ; // we just computed b = sqrt(n)
if (is_prime(n, steps)) return n;
do { positive_number res = factor_worker(n);
if (res != n) return res;
if (++steps % 96 == 0 && is_prime(n, 32)) return n ; // adjust it
} while (microtime() - begin < timeout);
return n;
}
The multiplier helper because computations are done modulo N :
static inline positive_number multiplication_modulo(positive_number lhs, positive_number rhs, positive_number mod) {
positive_number res = 0; // we avoid overflow in modular multiplication
for (lhs %= mod, rhs%= mod; rhs; (rhs & 1) ? (res = (res + lhs) % mod) : 0, lhs = (lhs << 1) % mod, rhs >>= 1);
return res; // <= (lhs * rhs) % mod
}
The prime checker helper, of course :
static int is_prime(positive_number n, int k) {
positive_number a = 0, b, c, d, e, f, g; int h, i;
if ((n == 1) == (n & 1)) return n == 2;
if (n < 51529) // fast constexpr check for small primes (removable)
return (n & 1) & ((n < 6) * 42 + 0x208A2882) >> n % 30 && (n < 49 || (n % 7 && n % 11 && n % 13 && n % 17 && n % 19 && n % 23 && n % 29 && n % 31 && n % 37 && (n < 1369 || (n % 41 && n % 43 && n % 47 && n % 53 && n % 59 && n % 61 && n % 67 && n % 71 && n % 73 && ( n < 6241 || (n % 79 && n % 83 && n % 89 && n % 97 && n % 101 && n % 103 && n % 107 && n % 109 && n % 113 && ( n < 16129 || (n % 127 && n % 131 && n % 137 && n % 139 && n % 149 && n % 151 && n % 157 && n % 163 && n % 167 && ( n < 29929 || (n % 173 && n % 179 && n % 181 && n % 191 && n % 193 && n % 197 && n % 199 && n % 211 && n % 223))))))))));
for (b = c = n - 1, h = 0; !(b & 1); b >>= 1, ++h);
for (; k--;) {
for (g = 0; g < sizeof(positive_number); ((char*)&a)[g++] = rand()); // random number
do for (d = e = 1 + a % c, f = n; (d %= f) && (f %= d););
while (d > 1 && f > 1);
for (d = f = 1; f <= b; f <<= 1);
for (; f >>= 1; d = multiplication_modulo(d, d, n), f & b && (d = multiplication_modulo(e, d, n)));
if (d == 1) continue;
for (i = h; i-- && d != c; d = multiplication_modulo(d, d, n));
if (d != c) return 0;
}
return 1;
}
The factorization worker, a single call does not guarantee a success, it's a probabilistic try :
positive_number factor_worker(positive_number n) {
size_t a; positive_number b = 0, c, d, e, f;
for (a = 0; a < sizeof(positive_number); ((char*)&b)[a++] = rand()); // pick random polynomial
c = b %= n;
do {
b = multiplication_modulo(b, b, n); if(++b == n) b = 0;
c = multiplication_modulo(c, c, n); if(++c == n) c = 0;
c = multiplication_modulo(c, c, n); if(++c == n) c = 0;
for (d = n, e = b > c ? b - c : c - b; e; f = e, e = multiplication_modulo(d / f, f, n), e = (d - e) % n, d = f);
// handle your precise timeout in the for loop body
} while (d == 1);
return d;
}
Example of usage :
#include <stdio.h>
positive_number exec(positive_number n) {
positive_number res = factor(n, 2); // 2 seconds
if (res == n) return res + printf("%llu * ", n) * fflush(stdout) ;
return exec(res) * exec(n / res);
}
int main() {
positive_number n = 0, mask = -1, res;
for (int i = 0; i < 1000;) {
int bits = 4 + rand() % 60; // adjust the modulo for tests
for (size_t k = 0; k < sizeof(positive_number); ((char*)&n)[k++] = rand());
// slice a random number with the "bits" variable
n &= mask >> (8 * sizeof (positive_number) - bits); n += 4;
printf("%5d. (%2d bits) %llu = ", ++i, bits, n);
res = exec(n);
if (res != n) return 1;
printf("1\n");
}
}
You can put it into a primes.c file then compile + execute :
gcc -O3 -std=c99 -Wall -pedantic primes.c ; ./a.out ;
Also, 128-bit integers GCC extension extension may be available.
Example output :
358205873110913227 = 380003149 * 942639223 took 0.01s
195482582293315223 = 242470939 * 806210357 took 0.0021s
107179818338278057 = 139812461 * 766597037 took 0.0023s
44636597321924407 = 182540669 * 244529603 took 0s
747503348409771887 = 865588487 * 863578201 took 0.016s
// 128-bit extension available output :
170141183460469231731687303715506697937 =
13602473 * 230287853 * 54315095311400476747373 took 0.646652s
Info : This C99 100 lines probabilistic factorization software proposition is based on a Miller–Rabin primality test followed or not by a Pollard's rho algo. Like you, i initially aimed to factorize just a little long long int. By my tests it's working fast enough to me, even for some larger. Thank you.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND.
