CODEWITHSUNDEEP
primesquadraticfactorizationsieve-algorithm
Bartemis
Bartemis

Reputation: 13

Finding number of divisors of a big integer using prime/quadratic factorization (C#)

I'm trying to get the number of divisors of a 64 bit integer (larger than 32 bit)

My first method (for small numbers) was to divide the number until the resulting number was 1, count the number of matching primes and use the formula (1 + P1)(1+ P2)..*(1 + Pn) = Number of divisors

For example:

24 = 2 * 2 * 2 * 3 = 2^3 * 3^1

==> (3 + 1)*(1 + 1) = 4 * 2 = 8 divisors

        public static long[] GetPrimeFactor(long number)
        {
            bool Found = false;
            long i = 2;
            List<long> Primes = new List<long>();
            while (number > 1)
            {
                if (number % i == 0)
                {
                    number /= i;
                    Primes.Add(i);
                    i = 1;
                }
                i++;
            }
            return Primes.ToArray();
        }

But for large integers this method is taking to many iterations. I found a method called Quadratic sieve to make a factorization using square numbers. Now using my script this can be much easier because the numbers are much smaller.

My question is, how can I implement this Quadratic Sieve?

Upvotes: 1

Views: 811

Answers (1)

user448810
user448810

Reputation: 17876

The quadatic sieve is a method of finding large factors of large numbers; think 10^75, not 2^64. The quadratic sieve is complicated even in simple pseudocode form, and much more complicated if you want it to be efficient. It is very much overkill for 64-bit integers, and will be slower than other methods that are specialized for such small numbers.

If trial division is too slow for you, the next step up in complexity is John Pollard's rho method; for 64-bit integers, you might want to trial divide up to some small limit, maybe the primes less than a thousand, then switch to rho. Here's simple pseudocode to find a single factor of n; call it repeatedly on the composite cofactors to complete the factorization:

function factor(n, c=1)
    if n % 2 == 0 return 2
    h := 1; t := 1
    repeat
        h := (h*h+c) % n
        h := (h*h+c) % n
        t := (t*t+c) % n
        g := gcd(t-h, n)
    while g == 1
    if g is prime return g
    return factor(g, c+1)

There are other ways to factor 64-bit integers, but this will get you started, and is probably sufficient for most purposes; you might search for Richard Brent's variant of the rho algorithm for a modest speedup. If you want to know more, I modestly recommend the essay Programming with Prime Numbers at my blog.

Upvotes: 2

Related Questions