Integer Factorization

There are several techniques for factoring integers. Most of these rely on algorithms with non-polynomial complexity, making them computationally challenging.

Sieve of Eratosthenes

One approach to factorization is based on the Sieve of Eratosthenes and follows this algorithm:

1. Divide \( n \) by successive integers \( a = 2,3,4,5, \dots, \sqrt{n} \).
2. Whenever \( n \) is divisible by \( a \), express it as \( n = a \cdot m \).
   • Add \( a \) to the list of factors.
   • Repeat the process with \( n = m \).

The algorithm terminates when \( n \) is reduced to 1.

Example

Factorizing 28:

$$ n = 28 $$

$$ 2 \mid 28 \Rightarrow n = \frac{28}{2} = 14 , f = \{2\} $$

Continuing with \( n = 14 \):

$$ 2 \mid 14 \Rightarrow n = \frac{14}{2} = 7 , f = \{2,2\} $$

Continuing with \( n = 7 \):

$$ 7 \mid 7 \Rightarrow n = \frac{7}{7} = 1 , f = \{2,2,7\} $$

Since \( n = 1 \), the process stops.

Thus, the prime factorization of 28 is:

$$ 2 \cdot 2 \cdot 7 $$

$$ 2^2 \cdot 7 $$

Note: While effective for small numbers, this method becomes computationally impractical for large integers, as the process has non-polynomial complexity.

Fermat’s Factorization Method

Fermat’s method provides an alternative approach to integer factorization but is only applicable to odd numbers.

1. Compute the integer part of \( \sqrt{n} \) and increment by 1: $$ k = \lfloor \sqrt{n} \rfloor + 1 $$
2. Check whether \( k^2 - n \) is a perfect square: $$ x = k^2 - n $$
   • If \( x \) is a perfect square, then \( n \) factors as: $$ (k-x) \cdot (k+x) $$
   • If not, increment \( k \) by 1 and repeat until \( x \) becomes a perfect square.

The resulting factorization may not necessarily consist of prime numbers.

Note: Fermat’s method is significantly more efficient than trial division, particularly for numbers with factors close to \( \sqrt{n} \). However, it remains an exponential-time algorithm in the worst case.

Example

Factorizing 69:

First, compute \( k \):

$$ k = \lfloor \sqrt{69} \rfloor + 1 = 8 + 1 = 9 $$

Now, check whether \( k^2 - n \) is a perfect square:

$$ x = 9^2 - 69 = 81 - 69 = 12 $$

Since 12 is not a perfect square, increment \( k \) and check again:

$$ x = 10^2 - 69 = 100 - 69 = 31 $$

$$ x = 11^2 - 69 = 121 - 69 = 52 $$

$$ x = 12^2 - 69 = 144 - 69 = 75 $$

$$ x = 13^2 - 69 = 169 - 69 = 100 $$

At \( k = 13 \), we find that \( x = 100 \), which is a perfect square.

Thus, the factorization of 69 is:

$$ (k-x) \cdot (k+x) $$

$$ (13-10) \cdot (13+10) $$

$$ 3 \cdot 23 $$

Therefore, the factors of 69 are 3 and 23.

Note: The factors obtained using Fermat’s method are not necessarily prime.

And so forth.