Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Integer Factorization
2.1.
Trial Divison Method
2.1.1.
Algorithm
2.1.2.
C++ Code
2.2.
Wheel Factorization Method
2.2.1.
Algorithm
2.2.2.
C++ Code
2.3.
Precomputed Primes Method
2.3.1.
C++ Code
2.4.
Fermat’s Factorization Method
2.4.1.
C++ Code
3.
Frequently Asked Questions
3.1.
What is a Prime Number?
3.2.
What is a Composite Number?
3.3.
What is Factorization?
3.4.
What are some common methods to find the prime factorization of a positive integer?
3.5.
What is called the Sieve of Eratosthenes?
4.
Conclusions
Last Updated: Mar 27, 2024
Medium

What are the Factoring Algorithms in Practice?

Author Rajat Agrawal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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. 

prime factorization

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 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;
}

Wheel Factorization Method

This method is an optimization over the Trial division method.

Algorithm

In this method, we will keep dividing the number 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 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;
}

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;
}

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 andhave 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;
}
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a Prime Number?

A prime number is a number that is divisible by 1 and itself. Some common prime numbers are 2, 3, 5, 7, 11, 13, 17, etc.

What is a Composite Number?

A composite number is a number that has more than two factors. Some common prime numbers are 4, 6, 8, 9, 10, 12, 14, etc.

What is Factorization?

Factorization is the process of dividing a bigger number into products of multiple smaller numbers.

What are some common methods to find the prime factorization of a positive integer?

Some common methods to find the prime factorization of a positive integer are Trial Divison Method, Wheel Factorization Method, Fermat’s Factorization Method, etc.

What is called the Sieve of Eratosthenes?

Sieve of Eratosthenes is a method to find prime numbers and composite numbers among a group of numbers.

Conclusions

In this article, we have extensively discussed different factoring algorithms used for integer factorization. 

If you want to learn more, check out our articles on What is the Rabin Cryptosystem?Message Authentication Codes in CryptographyNested MACs and HMAC in Cryptography, and CBC-MAC in Cryptography

Also, check out these exciting courses from coding ninjas to expand your knowledge, Coding CourseCode StudioInterview ExperienceGuided PathInterview ProblemsTest SeriesLibrary, and Resources

Happy Coding!

Previous article
Dixon’s Random Squares Algorithm
Next article
What are the Attacks on RSA?
Live masterclass