Introduction
As we all know, factorization divides a larger number into the products of several smaller numbers. Every positive number can be factored into the product of various prime numbers, but these products cannot be factored further into positive integers larger than one. The extremely difficult issue of factorizing huge positive integers has led to the creation of numerous cryptographic methods, including the RSA Cryptosystem. There are multiple algorithms available to aid in computing a positive integer's factors.
We'll talk about some significant integer factorization algorithms in this blog.
Integer Factorization
We'll talk about a few factoring algorithms now.
Method of Wheel Factorization
This approach is an improvement on the Trial division approach.
Algorithm
In this approach, we shall repeatedly divide n by 2. We do not need to check every other even integer after the number is not divisible by 2. We now only have to look for half the numbers. Then, we proceed by repeatedly dividing n by 3. However, the subsequent division step can discard all multiples of 3 if the value is not divisible by 3. There are only 33.3% of the numbers left for us to verify. We can create a list of primes to check and skip in this fashion.
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> WheelFactorization(ll num) {
vector<ll> divisor;
for (int a : {2, 3, 5}) {
while (num % a == 0) {
factor.push_back(a);
num /= a;
}
}
static array<int, 8> inc = {4, 2, 4, 2};
int i = 0;
for (ll a = 7; a * a <= num; a += inc[i++]) {
while (num % a == 0) {
factor.push_back(a);
num /= a;
}
if (i == 8)
i = 0;
}
if (num > 1)
divisor.push_back(num);
return divisor;
}
Method of Trial Divison
This is one of the most straightforward procedures for determining a positive integer's prime factorization.
Algorithm
We are given the prime factorization of the positive number n, which we must determine. We continue to divide num by each of its potential divisors, a. The notion that no single prime factor of a composite number can be larger than the square root of num is utilized in this situation.
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> TrialDivison(ll num)
{
vector<ll> divisors;
for (ll a = 2; a * a <= num; a++)
{
while (num % a== 0)
{
factors.push_back(a);
num /= a;
}
}
if (num > 1){
divisor.push_back(num);
}
return divisors;
}
Method of Precomputed Primes
This approach improves on the Wheel Factorization approach.
Algorithm
We know that the wheel factorization approach is extended, leaving us with just prime integers to verify. The Sieve of Eratosthenes method is the best way to calculate all the prime integers between 1 and num. I'll therefore use the Sieve of Eratosthenes to precalculate all prime numbers up to sqrt(n).
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> primes;
vector<ll> PrecomputedFactors(ll num)
{
vector<ll> divisors;
for (ll a : divisors)
{
if (a * a > num)
break;
while (num % a == 0)
{
divisors.push_back(a);
num /= a;
}
}
if (num > 1)
divisors.push_back(num);
return divisors;
}
Method of Fermat Factorization
This approach is based on the notion that the difference of the square of two numbers can be expressed as an odd integer.
Algorithm
An odd composite number, num = p * q, can be written as the difference of two squares, num = a - b. a = (p + q)/2 and b = (p - q)/2, respectively. This approach tries to take advantage of the fact by guessing the first square, a2, and then determining whether the remaining portion, b2, equals a2, minus a num is also a square number. If so, we have discovered the factors a - b and a + b for n. This process is more rapid. If the difference between two prime numbers, p, and q, is tiny, this approach operates more quickly. When p and q differ significantly, this method performs very slowly.
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll FermatMethod(ll num)
{
ll a = ceil(sqrt(num));
ll b = a * a - num;
ll ba = round(sqrt(b));
while (ba * ba != b)
{
a = a + 1;
b = a * a - num;
ba = round(sqrt(b));
}
return a - ba;
}