What are the Factoring Algorithms in Practice?

Introduction

As we know, factorization is the process of dividing a bigger number into products of multiple smaller numbers. Every positive integer can be factored into a product of prime numbers, which cannot be further factored into integers greater than 1. Factorization of very big positive integers is a highly complex task, and this fact is used to develop various cryptographic algorithms such as RSA Cryptosystem. Several algorithms are there that help compute factors of a positive integer. 

In this blog, we will discuss some important algorithms used for integer factorization.

Integer Factorization

Let’s discuss some factoring algorithms.

Trial Divison Method

This is one of the most basic algorithms to find the prime factorization of a positive integer.

Algorithm

We are given a positive integer n whose prime factorization we need to find. We keep dividing the number n with all the possible divisors d. The fact that is used here is that all the prime factors of a composite number cannot be bigger than the square root of n. So we need to test for d = 2 to d = sqrt(n). 

Time Complexity: O(sqrt(n)), since we need to run the algorithm till sqrt(n) time.

C++ Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll> TrialDivisonMethod(ll n)
{
    vector<ll> factors;
    for (ll d = 2; d * d <= n; d++)
    {
        while (n % d == 0)
        {
            factors.push_back(d);
            n /= d;
        }
    }
    if (n > 1){
        factors.push_back(n);
    }
    return factors;
}

You can also try this code with Online C++ Compiler

Run Code

Wheel Factorization Method

This method is an optimization over the Trial division method.

Algorithm

In this method, we will keep dividing the number n by 2. But once the number is not divisible by 2, we don't need to check every other even number. This leaves us to check for only 50% of the numbers. Then we keep dividing the number n by 3. But once the number is not divisible by 3, we can ignore all the multiples of 3 in the further division process. This leaves us to check for only 33.3% of the numbers. In this way, we can make a list of primes to check and skip.

Time Complexity: O(sqrt(n)), in the worst case.

C++ Code

We have implemented for the prime numbers 2, 3, and 5. 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

 
vector<ll> WheelFactorization(ll n) {
    vector<ll> factor;
    for (int d : {2, 3, 5}) {
        while (n % d == 0) {
            factor.push_back(d);
            n /= d;
        }
    }
    static array<int, 8> incre = {4, 2, 4, 2, 4, 6, 2, 6};
    int j = 0;
    for (ll d = 7; d * d <= n; d += incre[j++]) {
        while (n % d == 0) {
            factor.push_back(d);
            n /= d;
        }
        if (j == 8)
            j = 0;
    }
    if (n > 1)
        factor.push_back(n);
    return factor;
}

You can also try this code with Online C++ Compiler

Run Code

Precomputed Primes Method

This method is an optimization over the Wheel Factorization method. 

Algorithm

If we extend the wheel factorization method, we know that we are left with only prime numbers to check. The best method to compute all the prime numbers between 1 and n is by using the Sieve of Eratosthenes method. So will precompute all the prime numbers till sqrt(n) using the Sieve of Eratosthenes.

Time Complexity: O(sqrt(n)), in the worst case.

C++ Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll> primes;

vector<ll> PrecomputedPrimes(ll n)
{
    vector<ll> factor;
    for (ll d : primes)
    {
        if (d * d > n)
            break;
        while (n % d == 0)
        {
            factor.push_back(d);
            n /= d;
        }
    }
    if (n > 1)
        factor.push_back(n);
    return factor;
}

You can also try this code with Online C++ Compiler

Run Code

Fermat’s Factorization Method

This method is based on the fact that an odd integer can be written as the difference between the square of two numbers.

Algorithm

We can write an odd composite number  n = p * q  as the difference of two squares  n = a^2 - b^2. Where a = (p + q)/2 and b = (p - q)/2. This method tries to exploit the fact by guessing the first square a^2 , and checking if the remaining part  b^2 = a^2 - n  is also a square number. If it is, then we have found the factors  a - b and  a + b  of  n . This method works faster if the difference between two primes p and q is small. For p and q have a very huge difference, this algorithm runs very slowly.

Time Complexity: O(|p - q|), in the worst case.

C++ Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll FermatFactorization(ll n)
{
    ll a = ceil(sqrt(n));
    ll b_sqr = a * a - n;
    ll b = round(sqrt(b_sqr));
    while (b * b != b_sqr)
    {
        a = a + 1;
        b_sqr = a * a - n;
        b = round(sqrt(b_sqr));
    }
    return a - b;
}

You can also try this code with Online C++ Compiler

Run Code