Pollard Rho factorization method implementation

Question

Every time I factor a number using Pollard Rho factorization method is it necessary to check for its primality before Pollard Rho factorization ? If yes then I have to implement Miller Rabin's primality test or any primality test each time I want to factor any number and stil I have to take care of strong pseudoprimes , isn't it complex ? Is there any simpleand still faster way to handle this ? (I am using these tests on numbers upto 10 digits)

Answer 1

Yes, you must check before you apply Pollard Rho that the number you are factoring is composite. If it is prime, the gcd step will always return 1, because a prime number is always co-prime to every other number, and Pollard Rho will run forever without result.

For numbers up to ten digits, Pollard Rho is not necessary. Simple trial division will be quick enough, since you only need the primes less than 100000, and there are only 9592 of them.

Answer 2

You can try this ~100 lines C implementation of Pollard Rho :

There is some helpers :

#include <stdlib.h>
#include <stdint.h>

typedef uint_fast64_t num ;

static inline num mul_mod(num a, num b, const num mod) {
    // Return (a * b) % mod, avoiding overflow errors while doing modular multiplication.
    num res = 0, tmp;
    for (b %= mod; a; a & 1 ? b >= mod - res ? res -= mod : 0, res += b : 0, a >>= 1, (tmp = b) >= mod - b ? tmp -= mod : 0, b += tmp);
    return res % mod;
}

static inline num square_root(num n) {
    // Return the number that was multiplied by itself to reach N.
    num a = 0, b, c;
    for (b = 1ULL << 62; b; c = a + b, n -= c &= -(n >= c), a = (a >> 1) | (c & b), b >>= 2);
    // Variable n contains the remainder.
    return a;
}

There is a required prime checker :

static  int is_prime(const num n, size_t iterations) {
    // Perform a Miller-Rabin (strong probable prime) test.
    num a = 0, b, c, d, e, f; int h, i;
    if ((n == 1) == (n & 1)) return n == 2;
    for (b = c = n - 1, h = 0; !(b & 1); b >>= 1, ++h);
    for (; iterations--;) {
        for (size_t g = 0; g < sizeof(a); ((char*)&a)[g++] = rand()); // random input.
        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 = mul_mod(d, d, n), f & b && (d = mul_mod(e, d, n)));
        if (d == 1) continue;
        for (i = h; i-- && d != c; d = mul_mod(d, d, n));
        if (d != c) return 0;
    }
    return 1;
}

There is two factorization functions :

static inline num factor_worker_2(const num n, size_t limit) {
    // Perform a Pollard's Rho probabilistic test.
    size_t a = -1, b = 2;
    num c, d = 1 + rand(), e = 1, f = 1;
    for (c = d %= n; f == 1 && --limit; d = c, b <<= 1, a = -1) {
        for (; f |= e, f == 1 && ++a != b;) {
            c = mul_mod(c, c, n);
            for (++c, c *= c != n, e = n, f = c > d ? c - d : d - c; (f %= e) && (e %= f););
        }
    }
    return f;
}

static inline num factor_worker_1(const num n) {
    // Perform a trial divisions test on N.
    static const num list[] = {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, 1};
    size_t i;
    for (i = -1; n % list[++i];);
    return list[i];
}

There is a factorizarion manager :

num factor(const num n) {
// Basic factorization manager, detect primes, perfect squares, execute workers.
    num res;
    switch (n) {
        case 0: case 1: case 2: case 3:
            res = 1; break;
        default:
            res = factor_worker_1(n);
            if (res == 1 && !is_prime(n, 20)) {
                res = square_root(n);
                if (res * res != n)
                    for(;res = factor_worker_2(n, -1), res == 1 || res == n;);
            }
    }
    return res;
}

There is a main :

#include <assert.h>
#include <stdio.h>

int main(void) {
    num N;
    N = 951818131364430049;
    printf("factor is %zu\n", factor(N));
}

To try it :

// You can put it into a main.c file then compile + execute :
// gcc -O3 -std=c99 -Wall -pedantic main.c ; ./a.out ;

Normally you can Try it Online, here is the source for more informations, Thank You.

Answer 3

Pollard-rho is absolutely not trivial.

The pollard-rho algorithm has a parameter c, and you use it with c=1, c=2, and so on.

There is a function f(p, c) such that if N has a prime factor p, then pollard-rho with parameter c will find that prime factor after exactly f(p, c) steps, where f(p, c) is about the size of the square root of p, and independent of N.

There is a problem: If N has prime factors p and q, and f(p, c) = f(q, c) then pollard-rho finds the factor r = pq. Worst case, if N=pq then it will find the factor N :-(

You check whether r and N/r are prime. If yes you found one or two factors. The rest can be factored with a different parameter instead of c.

You have a problem if N is prime. Running pollard-rho to the end would find that N has a factor N after about sqrt(N) steps, while one of two or more prime factors is usually found after about N^(1/4) steps. So you run pollard for at most 5 N^(1/4) steps, then check N for primality.

If you find a factor r after k steps, and it is prime, then r is about k^2; if it is composite then r is at least about k^4. If say r > k^3 then you try to factor it with a different parameter.