Table of Contents

Prime Factorization

n = p₁a₁ × p₂a₂ × ... × pₖaₖ
Where:
pᵢ are prime numbers
aᵢ are positive integers

Introduction to Prime Factorization

Prime factorization is the process of decomposing a composite number into a product of prime numbers. This fundamental concept in number theory has applications ranging from cryptography to computer science and pure mathematics.

Fundamental Theorem of Arithmetic:

Every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors.

n = p₁a₁ × p₂a₂ × ... × pₖaₖ

Examples:

60 = 2² × 3 × 5

84 = 2² × 3 × 7

1001 = 7 × 11 × 13

123456789 = 3² × 3607 × 3803

In this comprehensive guide, we'll explore various prime factorization methods from basic to advanced, with detailed algorithms, complexity analysis, and interactive tools.

What is Prime Factorization?

Prime factorization breaks down composite numbers into their prime components. Understanding this process is crucial for many areas of mathematics and computer science.

Key Concepts
  • Prime Number: A natural number greater than 1 that has no positive divisors other than 1 and itself
  • Composite Number: A natural number greater than 1 that is not prime
  • Prime Factor: A prime number that divides the given number
  • Multiplicity: The exponent of a prime factor in the factorization

Factorization Tree for 360:

360
↓
2 × 180
    ↓
    2 × 90
        ↓
        2 × 45
            ↓
            3 × 15
                ↓
                3 × 5

Result: 360 = 2³ × 3² × 5

Practice effectively and measure your knowledge with the factor-calculator.

Trial Division Method

The simplest and most intuitive method for prime factorization. It tests divisibility by each prime number up to the square root of n.

🔍

Basic Trial Division

Basic Time: O(√n)

Test divisibility by all integers from 2 up to √n.

// Basic Trial Division Algorithm
function trialDivision(n) {
  let factors = [];
  let d = 2;
  while (n > 1) {
    while (n % d == 0) {
      factors.push(d);
      n /= d;
    }
    d++;
  }
  return factors;
}
⚡

Optimized Trial Division

Intermediate Time: O(√n)

Test only primes and handle 2 separately for efficiency.

// Optimized Trial Division
function optimizedTrialDivision(n) {
  let factors = [];
  // Handle factor 2
  while (n % 2 == 0) {
    factors.push(2);
    n /= 2;
  }
  // Handle odd factors
  for (let i = 3; i*i <= n; i += 2) {
    while (n % i == 0) {
      factors.push(i);
      n /= i;
    }
  }
  if (n > 1) factors.push(n);
  return factors;
}
Trial Division Example: Factorizing 84
  1. Start with n = 84
  2. Divide by 2: 84 ÷ 2 = 42, factor = 2
  3. Divide by 2: 42 ÷ 2 = 21, factor = 2
  4. Divide by 3: 21 ÷ 3 = 7, factor = 3
  5. Divide by 7: 7 ÷ 7 = 1, factor = 7
  6. Result: 84 = 2² × 3 × 7

Take your learning further by testing it through the factor-calculator.

Sieve Methods

Sieve methods pre-compute prime numbers to speed up factorization. The Sieve of Eratosthenes is the most famous example.

⚙️

Sieve of Eratosthenes

Intermediate Time: O(n log log n)

Efficient algorithm for finding all primes up to a given limit.

// Sieve of Eratosthenes
function sieve(limit) {
  let isPrime = new Array(limit+1).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i*i <= limit; i++) {
    if (isPrime[i]) {
      for (let j = i*i; j <= limit; j += i) {
        isPrime[j] = false;
      }
    }
  }
  return isPrime;
}
🚀

Segmented Sieve

Advanced Memory: O(√n)

Process numbers in segments to handle large ranges with limited memory.

// Segmented Sieve Concept
function segmentedSieve(low, high) {
  // Generate primes up to √high
  let limit = Math.floor(Math.sqrt(high));
  let primes = simpleSieve(limit);
  
  // Process segments
  let segmentSize = high - low + 1;
  let isPrime = new Array(segmentSize).fill(true);
  
  // Mark multiples in segment
  for (let p of primes) {
    let start = Math.max(p*p, Math.ceil(low/p)*p);
    for (let j = start; j <= high; j += p) {
      isPrime[j-low] = false;
    }
  }
  return isPrime;
}

Sieve Visualization

Enter a limit and click "Generate Primes"

Pollard's Rho Algorithm

A probabilistic algorithm for integer factorization. It's particularly effective for composite numbers with small prime factors.

⚡

Pollard's Rho Algorithm

Advanced Time: O(n¹/⁴)

Uses Floyd's cycle-finding algorithm and random polynomial functions to find factors.

Algorithm Steps
  1. Choose random values x, c, and set y = x
  2. Define function f(x) = (x² + c) mod n
  3. Compute d = gcd(|x - y|, n)
  4. If d = 1, update x = f(x), y = f(f(y))
  5. If d = n, restart with different parameters
  6. If 1 < d < n, d is a non-trivial factor
// Pollard's Rho Algorithm
function pollardRho(n) {
  if (n % 2 == 0) return 2;
  if (isPrime(n)) return n;
  
  let x = 2, y = 2, d = 1;
  let c = Math.floor(Math.random() * (n-2)) + 1;
  
  const f = (x) => (x*x + c) % n;
  
  while (d == 1) {
    x = f(x);
    y = f(f(y));
    d = gcd(Math.abs(x - y), n);
  }
  
  return d == n ? pollardRho(n) : d;
}

Example: Factor 8051 using Pollard's Rho

Let f(x) = x² + 1 mod 8051

Start with x = y = 2, c = 1

After iterations: gcd(|x-y|, 8051) = 97

8051 = 97 × 83

Challenge yourself with real-case scenarios using the factor-calculator.

Fermat's Factorization Method

Based on the difference of squares identity: n = a² - b² = (a - b)(a + b). Effective when factors are close to √n.

🎯

Fermat's Factorization

Intermediate Time: O((a-√n))
Algorithm Steps
  1. Compute a = ⌈√n⌉
  2. Calculate b² = a² - n
  3. If b² is a perfect square, factors are (a - b) and (a + b)
  4. Otherwise, increment a and repeat
// Fermat's Factorization Method
function fermatFactor(n) {
  let a = Math.ceil(Math.sqrt(n));
  let b2 = a*a - n;
  
  while (!isPerfectSquare(b2)) {
    a++;
    b2 = a*a - n;
  }
  
  let b = Math.sqrt(b2);
  return [a - b, a + b];
}

Example: Factor 5959 using Fermat's Method

√5959 ≈ 77.19, so a = 78

b² = 78² - 5959 = 6084 - 5959 = 125 (not a perfect square)

a = 79: b² = 6241 - 5959 = 282

a = 80: b² = 6400 - 5959 = 441 = 21² ✓

Factors: (80 - 21) = 59 and (80 + 21) = 101

5959 = 59 × 101

Elliptic Curve Method (ECM)

An advanced factorization algorithm that uses elliptic curves over finite fields. Particularly effective for medium-sized factors.

🌀

Elliptic Curve Method

Advanced Time: O(e^(√(2 log p log log p)))

ECM works by performing elliptic curve operations modulo n. If a computation fails, it likely reveals a factor of n.

ECM Algorithm Overview
  1. Choose random elliptic curve E and point P on E
  2. Compute Q = kP (scalar multiplication) modulo n
  3. During computation, if inversion fails modulo n, gcd gives a factor
  4. Repeat with different curves and bounds
// ECM Conceptual Implementation
function ecmFactor(n, B1 = 10000, curves = 10) {
  for (let i = 0; i < curves; i++) {
    // Choose random curve parameters
    let a = randomInt(1, n-1);
    let b = randomInt(1, n-1);
    let P = [randomInt(1, n-1), randomInt(1, n-1)];
    
    // Stage 1: Compute Q = kP where k = lcm(1..B1)
    try {
      let Q = ellipticMultiply(P, computeK(B1), a, b, n);
    } catch (e) {
      // Inversion failed - we found a factor!
      return extractFactor(e, n);
    }
  }
  return null; // No factor found
}

Evaluate your understanding using hands-on problems in the factor-calculator.

Interactive Factorization Tool

Prime Factorization Calculator

Enter any integer to see its prime factorization using different methods.

Enter a number and choose a method to see its prime factorization.

Challenge: Factor 1234567890 using trial division. How many prime factors does it have?

Solution:

1234567890 = 2 × 3² × 5 × 3607 × 3803

It has 5 prime factors (counting multiplicities).

Step-by-step:

  1. Divide by 2: 1234567890 ÷ 2 = 617283945
  2. Divide by 3: 617283945 ÷ 3 = 205761315
  3. Divide by 3: 205761315 ÷ 3 = 68587105
  4. Divide by 5: 68587105 ÷ 5 = 13717421
  5. Divide by 3607: 13717421 ÷ 3607 = 3803
  6. Divide by 3803: 3803 ÷ 3803 = 1
Challenge: Use Fermat's method to factor 2047. What are its factors?

Solution:

2047 = 23 × 89

Fermat's Method:

  1. √2047 ≈ 45.24, so a = 46
  2. b² = 46² - 2047 = 2116 - 2047 = 69 (not square)
  3. a = 47: b² = 2209 - 2047 = 162
  4. a = 48: b² = 2304 - 2047 = 257
  5. a = 49: b² = 2401 - 2047 = 354
  6. a = 50: b² = 2500 - 2047 = 453
  7. a = 51: b² = 2601 - 2047 = 554
  8. a = 52: b² = 2704 - 2047 = 657
  9. a = 53: b² = 2809 - 2047 = 762
  10. a = 54: b² = 2916 - 2047 = 869
  11. a = 55: b² = 3025 - 2047 = 978
  12. a = 56: b² = 3136 - 2047 = 1089 = 33² ✓

Factors: (56 - 33) = 23 and (56 + 33) = 89

Complexity Analysis

Understanding the time and space complexity of factorization algorithms helps choose the right method for different scenarios.

Method Time Complexity Space Complexity Best For Worst Case
Trial Division O(√n) O(1) Small numbers n is prime
Sieve + Trial O(√n) O(√n) Multiple factorizations Large n
Pollard's Rho O(n¹/⁴) O(1) Numbers with small factors n = p × q (similar size)
Fermat's Method O((a-√n)) O(1) Factors close to √n Factors far apart
Elliptic Curve O(e^(√(2 log p log log p))) O(1) Medium-sized factors Large prime factors
Quadratic Sieve O(e^(√(log n log log n))) O(√n) Large numbers (up to 100 digits) Very large n
General Number Field Sieve O(e^((log n)^(1/3) (log log n)^(2/3))) Large Very large numbers (>100 digits) RSA numbers

Trial Division

✓ Simple to implement

✓ Deterministic

✗ Exponential time

Best for n < 10⁶

Pollard's Rho

✓ Fast for small factors

✓ Low memory usage

✗ Probabilistic

Best for n < 10¹²

Quadratic Sieve

✓ Sub-exponential

✓ Practical for 50-100 digits

✗ High memory

Best for 10⁵⁰ to 10¹⁰⁰

General Number Field Sieve

✓ Fastest known for large n

✓ Used for RSA challenges

✗ Complex implementation

Best for n > 10¹⁰⁰

Evaluate your understanding using hands-on problems in the factor-calculator.

Applications of Prime Factorization

Prime factorization has numerous practical applications in computer science, cryptography, and mathematics.

🔐

Cryptography

RSA Encryption: Security relies on difficulty of factoring large numbers

Key Generation: Creating public/private key pairs

Digital Signatures: Verification using prime factorization

Modern cryptography depends on the computational hardness of integer factorization.

🧮

Number Theory

GCD/LCM Computation: Using prime factorizations

Divisor Counting: τ(n) = ∏(aᵢ + 1)

Euler's Totient: φ(n) = n ∏(1 - 1/pᵢ)

Many number-theoretic functions are easily computed from prime factorization.

💻

Computer Science

Algorithm Design: Example of different complexity classes

Random Number Generation: Testing and generating primes

Complexity Theory: Study of computational hardness

Factorization algorithms demonstrate important CS concepts.

🎲

Mathematics Competitions

Olympiad Problems: Many problems involve factorization

Divisibility Rules: Derived from prime factors

Diophantine Equations: Solving using factorization

Prime factorization is essential for mathematical problem-solving.

RSA Cryptography Example

Key Generation:

  1. Choose two large primes: p = 61, q = 53
  2. Compute n = p × q = 3233
  3. Compute φ(n) = (p-1)(q-1) = 3120
  4. Choose e = 17 (coprime to φ(n))
  5. Compute d = e⁻¹ mod φ(n) = 2753

Public Key: (n=3233, e=17)

Private Key: (n=3233, d=2753)

Security relies on difficulty of factoring 3233 back to 61 × 53

Put your learning into action with real examples on the factor-calculator.

Continue Your Number Theory Journey

Explore more number theory concepts to deepen your understanding:

Advanced Factorization Techniques

Learn efficient and advanced methods for breaking numbers into factors for deeper mathematical analysis.

History of Perfect Numbers

Explore the origins, discoveries, and mathematical importance of perfect numbers through history.

GCD and LCM Applications

Understand how Greatest Common Divisor and Least Common Multiple are used in real-world problem solving.

Prime Factorization Methods

Master multiple techniques for breaking numbers into prime factors with clear step-by-step approaches.