Factorization

Factorization refers to expressing an integer as a product of its prime factors. Efficient factorization algorithms have applications in cryptography and math.

Some common methods:

• Trial division - Test divisions by primes up to sqrt(n)
• Fermat’s factorization - Express n as difference of squares
• Pollard’s rho - Find factorization using random sequences

Java example - Trial division:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

List<Integer> factor(int n) {
  List<Integer> factors = new ArrayList<>();
  
  for (int i = 2; i*i <= n; i++) {
    while (n % i == 0) {
      factors.add(i);
      n /= i;
    }
  }

  if (n > 1) factors.add(n);
  
  return factors;
}

C++ example - Pollard’s rho:

1
2
3
4

vector<int> pollardRho(int n) {
  // Pollard rho algorithm
  return {p, q}; 
}

Python example - Fermat’s factorization:

1
2
3
4
5
6
7
8
9

import math

def fermat(n):

  a = math.ceil(math.sqrt(n))
  b2 = a*a - n
  b = math.sqrt(b2)

  return int(a+b), int(a-b)

Factorization provides the fundamental primes comprising a composite number. Useful for many number theoretic algorithms.

Minimum Factorization

The minimum factorization of an integer n is the smallest prime number that divides n. It can be found efficiently and provides a useful primitive for many algorithms.

Some approaches:

• Try all primes up to √n
• Use smallest prime factor of n-1
• Wheel factorization

Java example:

1
2
3
4
5
6
7
8

int minFactor(int n) {
  if (n % 2 == 0) return 2;

  for (int i = 3; i*i <= n; i += 2) {
    if (n % i == 0) return i;
  }
  return n;
}

C++ example:

1
2
3
4
5
6
7
8

int minFactor(int n) {
  if (n % 2 == 0) return 2;
  
  for (int i = 3; i*i <= n; i+=2) {
    if (n % i == 0) return i;
  }
  return n; 
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import math

def min_factor(n):

  if n % 2 == 0:
    return 2
  
  for i in range(3, int(math.sqrt(n)) + 1, 2):
    if n % i == 0:
      return i

  return n

Finding the smallest prime factor quickly is useful as a subroutine in various algorithms like factorization and primality testing.