Integer Factorization Algorithms

Greetings reader!
As we probably might know, In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. Mainly, A special-purpose factoring algorithm’s running time depends on the properties of the number to be factored or on one of its unknown factors: size, special form, etc. The parameters which determine the running time vary among algorithms.

We will discuss:
1. Trial division
2. Wheel factorization
3. Pollard’s p − 1 algorithm
4. Fermat’s factorization method
5. Brent’s Algorithm

1. Trial Division Method

The primality check can be performed more efficiently by the concept of the trial division method. The Trial Division method is one of the crucial but one of the easiest factorization techniques when dealing with integer factorization.
The essential idea behind trial division tests to see if an integer n, the integer to be factored, can be divided by each number in turn that is less than n.
To see if an individual small integer is prime, the trial division works well: just divide by all the primes less than (or equal to) its square root. For example, to show 211 is prime, just divide by 2, 3, 5, 7, 11, and 13. Since none of these divides the number evenly, it is a prime.

When looking for a large prime (say a titanic prime), we could never divide by all the primes less than the square root. However, we still use trial division for pre-screening: that is, when we want to know if n is prime, we first divide by a few million small primes, then apply a primality test.

Observation: The above method works with the observation that the maximum factor for any number N is always less than or equal to the square root(N). This conclusion can be derived in the following way:

From the school arithmetics, it is a known fact that any composite number is built out of two or more prime numbers.

Let the factors of N be n1, n2, and so on. The factors are largest only when there exist two factors n1 and n2 for the number N.

Therefore, let’s assume n1 and n2 are the two largest factors for the number N. These numbers n1 and n2 can be largest only when both n1 and n2 are equal.

Let n1 = n2 = n. Therefore, N = n * n. Hence, the largest possible factor for N is square root(N).

Approach: From the above observation, the approach for this algorithm is straightforward. The idea is instead of checking till N — 1 for a factor, we only check until square root(N).

Even so, this is a quite satisfactory method, considering that even the best-known algorithms have exponential time growth. For a chosen uniformly random, it can be shown that 88% of all positive integers have a factor under 100 and that 92% have a factor under 1000. Thus, when confronted by an arbitrary large a, it is worthwhile to check for divisibility by the small primes, since for {\displaystyle a=1000}a=1000, in base-2 {\displaystyle n=10}n=10.

However, many-digit numbers that do not have factors in the small primes can require days or months to factor with the trial division. In such cases, other methods are used.

2. Wheel Factorization Method
Wheel Factorization is the improvement of the method Sieve of Eratosthenes. For wheel factorization, one starts from a small list of numbers, called the basis — generally the first few prime numbers, then one generates the list, called the wheel, of the integers that are coprime with all numbers of the basis. Then to find the smallest divisor of the number to be factorized, one divides it successively by the numbers on the basis, and in the wheel.

Let say we select basis as {2, 3, 5} and the numbers which are coprime to the basis are {7, 11, 13, 17, 19, 23, 29, 31} are set as the wheel.

To understand it more, see the pattern in the above image that the numbers exhibit. The LCM of the first three Prime Numbers is 30. The numbers(less than 30) which are ending with 7, 1, and 3 and are not a multiple of 2, 3, and 5 and are always prime i.e {7, 11, 13, 17, 19, 23, 29}. Adding the no. 31 to this list and then if we add multiples of 30 to any of the numbers in the list, it gives us a Prime Number.

Algorithm for Wheel Factorization Method:

For the number N to be Prime or not:

bool isPrime(x) {

if (x < 2) {

return False;

}

for N in {2, 3, 5} {

return False;

}

for p= [0, sqrt(N)] such that p = p + 30: {

for c in [p+7, p+11, p+13, p+17, p+19, p+23, p+29, p+31] {

if c > sqrt(N)

break;

else if N % (c+p) = 0:

return False;

}

}

}

return True;

}

Approach:

Following is the approach for the above algorithm:

1. For the Primality Test of a given Number N, check if the given number is divisible by any of the numbers 2, 3, 5, or not.
2. If the number is not divisible by any of 2, 3, 5, then check if the number formed by adding multiples of 30 in the list [7, 11, 13, 17, 19, 23, 29, 31] divides the given number N or not. If Yes then the given number is not a Prime Number, else it is a Prime Number.

3. Fermat’s Factorization
Fermat’s Factorization states that any Odd Composite Number can be written as the difference between the Square of 2 numbers.
For instance,
We Can write a Odd Composite ‘n’

n = a.b where a > b, and the also as and n = x2 − y2

Proof :

a = x + y;

b = x — y;

Adding and Subtracting we get,

a + b = 2x;

a — b = 2y;

Solving for the values of x and y we get,

x = (a + b)/2;

y = (a — b)/2;

Therefore :

x^2 − y^2 = [((a+b)/2)^2 — ((a-b)/2)^2] ;

Simplifying the above equation we get,

x^2 − y^2 = [4ab/4] ;

x^2 − y^2 = a.b; // hence Proved.

Pseudo code to check the fermat factors of a given Number:

int fermat(int n) {

int a = ceil(sqrt(n));

int b2 = a*a — n;

int b = round(sqrt(b2));

while (b * b != b2) {

a = a + 1; b2 = a*a — n;

b = round(sqrt(b2));

}

return a — b;

}

Notice, this factorization method can be very fast if the difference between the two factors a and b is small. The algorithm runs in O(|a−b|)

O(|a−b|) time. However, since it is very slow, once the factors are far apart, it is rarely used in practice.

However, there are still a huge number of optimizations for this approach. E.g. by looking at the squares ‘a2’ modulo a fixed small number, you can notice that you don’t have to look at certain values ‘a’ since they cannot produce a square number a2 −n.

4. Pollard’s p − 1 Algorithm
Pollard’s p − 1 algorithm is a number-theoretic integer factorization algorithm; it was invented by John Pollard in 1974. It is a special-purpose algorithm, meaning that it is only suitable for integers with specific types of factors; it is the simplest example of an algebraic group factorization algorithm. This algorithm is an approach to find out prime factors of any integer factoring a large odd integer, n, into its corresponding prime factors can prove to be a difficult task. Using the combined help of modular exponentiation and GCD, it can calculate all the distinct prime factors in no time. The factors it finds are ones for which the number preceding the factor, p − 1, is power smooth; the essential observation is that, by working in the multiplicative group modulo a composite number N, we are also working in the multiplicative groups' modulo all of N’s factors.

Algorithm

Given a number n.
Initialise a = 2, I = 2

Until a factor is returned do
a <- (a^i) mod n
d <- GCD(a-1, n)
if 1 < d < n then
return d
else
i <- i+1

Other factor, d’ <- n/d

If d’ is not prime
n <- d’
goto 1
else
d and d’ are two prime factors.

In the above algorithm, the power of ‘a’ is continuously raised until a factor, ‘d’, of n is obtained. Once d is obtained, another factor, ‘d”, is n/d. If d’ is not prime, the same task is repeated for d’

5. Brent’s Algorithm

Brent’s algorithm uses two-pointer techniques. In this, we make one pointer stationary till every iteration and teleport it to another pointer at every power of two. The start of the cycle is determined by the smallest power of two at which they meet.

The smallest power of two where the two pointers meet is the starting point of the cycle. The algorithm is used to find the cycle in a linked list. The algorithm uses the slow and fast pointer approach but implementation is different. This improves upon the constant factor of Floyd’s algorithm by reducing the number of calls.

Brent's algorithm is Quadratic. Brent's Algorithm finds the length of the loop within the cycle detection loop itself. No need to traverse the loop again for counting the nodes in the loop.

Comparison with Floyd’s Algorithm:

1) Find the length of the loop in the first cycle detection loop itself. No extra work is required for this.

2) We only move second in every iteration and avoid moving first (which can be costly if moving to the next node involves evaluating a function).

Pseudocode for the algorithm-

1. Move the fast pointer (or second_pointer) in powers of 2 until we find a loop. After every power, we reset the slow pointer (or first_pointer) to the previous value of the second pointer. Reset length to 0 after every power.
2. The condition for loop testing is that the first_pointer and second_pointer become the same. And the loop is not present if second_pointer becomes NULL.
3. When we come out of a loop, we have a length of loop.
4. We reset first_pointer to head and second_pointer to node at position head + length.
5. Now we move both pointers one by one to find the beginning of the loop.

Time Complexity: O(m + n) where m is the smallest index of the sequence which is the beginning of a cycle, and n is the cycle’s length.

Auxiliary Space: O(1) auxiliary

Space complexity: O(1)

Thank you for reading the blog. Please share if you find it helpful.
Comment your feedback!

Blog By,
Kapil Kadadas | CS-A85 | 1711011
Akshay Kadam | CS-A86 | 1710490
Saurav Kendre | CS-A95 |1710219
Rishabh Parmar | CS-B37 | 1710961
Prathamesh Yejare | CS-B115 | 161864