Prime Factorization With Deterministic Miller-Rabin Up to 10^24

Trial division works for small numbers but chokes on 12-digit primes. Miller-Rabin is probabilistic in general, but with the right set of 12 witnesses it becomes deterministic for all n below 3.3 × 10^24 — well beyond JavaScript's 2^53 safe integer limit. Combined with wheel factorization for the factoring itself, this handles any number JS can represent.

Number theory tools are a classic programming exercise. "Given n, factor it and tell me everything about it" involves primes, divisors, Euler's totient, perfect numbers, and a bunch of other quantities that are conceptually simple but algorithmically tricky to do fast.

🔗 Live demo: https://sen.ltd/portfolio/prime-factorize/
📦 GitHub: https://github.com/sen-ltd/prime-factorize

Features:

• Prime factorization up to ~10^15
• Deterministic Miller-Rabin primality (12 witnesses)
• Sieve of Eratosthenes for primesUpTo(n)
• Divisor list, count, sum
• Euler's totient φ(n)
• GCD / LCM
• Perfect / abundant / deficient classification
• Next / previous prime
• Factorization tree visualization
• Japanese / English UI
• Zero dependencies, 75 tests

Miller-Rabin with deterministic witnesses

The Miller-Rabin primality test is probabilistic: for each "witness" a, it either reports "n is composite" definitively, or "n might be prime". With random witnesses you get a probability that falls with more iterations.

The trick: for bounded n, specific witness sets give deterministic results. For all n < 3.3 × 10^24, the 12 witnesses [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] are sufficient. This is a proven result from number theory.

const WITNESSES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37];

export function isPrime(n) {
  if (n < 2) return false;
  if (n < 4) return true;
  if (n % 2 === 0) return false;

  // Small cases: trial division
  if (n < 1e6) return trialDivision(n);

  // Miller-Rabin for larger
  let d = n - 1;
  let r = 0;
  while (d % 2 === 0) { d /= 2; r++; }

  for (const a of WITNESSES) {
    if (a >= n) continue;
    let x = modPow(a, d, n);
    if (x === 1 || x === n - 1) continue;
    let composite = true;
    for (let i = 0; i < r - 1; i++) {
      x = (x * x) % n;
      if (x === n - 1) { composite = false; break; }
    }
    if (composite) return false;
  }
  return true;
}

modPow(a, d, n) computes a^d mod n using fast exponentiation — O(log d) multiplications. Each witness round is O(log n), so the total is O(k log n) for k witnesses. For 12-digit inputs this runs in microseconds.

Wheel factorization

Pure trial division checks every number from 2 to sqrt(n). Wheel factorization skips multiples of small primes using a "wheel":

const WHEEL_PRIMES = [2, 3, 5];
const WHEEL_STEPS = [4, 2, 4, 2, 4, 6, 2, 6]; // offsets after 30k

export function factorize(n) {
  const factors = [];
  for (const p of WHEEL_PRIMES) {
    let e = 0;
    while (n % p === 0) { n /= p; e++; }
    if (e > 0) factors.push([p, e]);
  }

  let i = 7;
  let wi = 0;
  while (i * i <= n) {
    let e = 0;
    while (n % i === 0) { n /= i; e++; }
    if (e > 0) factors.push([i, e]);
    i += WHEEL_STEPS[wi];
    wi = (wi + 1) % WHEEL_STEPS.length;
  }
  if (n > 1) factors.push([n, 1]);
  return factors;
}

The wheel skips all multiples of 2, 3, and 5 after the initial small-prime extraction. This reduces the number of candidates to check by ~73% compared to checking every odd number.

Euler's totient

φ(n) counts integers 1..n that are coprime to n. For a factorization p₁^a₁ · p₂^a₂ · ... · pₖ^aₖ:

φ(n) = n · Π(1 - 1/pᵢ)

export function totient(n) {
  if (n === 1) return 1;
  const factors = factorize(n);
  let result = n;
  for (const [p] of factors) {
    result = result - result / p;
  }
  return result;
}

One pass through distinct primes — no need to check every integer below n. φ(12) = 12 · (1 - 1/2) · (1 - 1/3) = 12 · 0.5 · 0.667 = 4. (The coprimes to 12 are 1, 5, 7, 11.)

Perfect numbers

A perfect number equals the sum of its proper divisors. 6 = 1 + 2 + 3. 28 = 1 + 2 + 4 + 7 + 14. The first few perfect numbers are 6, 28, 496, 8128, 33550336. Every known perfect number is even, and it's an open question whether odd perfect numbers exist at all.

export function isPerfect(n) {
  return sumOfDivisors(n) - n === n; // sum of proper divisors
}

Series

This is entry #81 in my 100+ public portfolio series.

• 📦 Repo: https://github.com/sen-ltd/prime-factorize
• 🌐 Live: https://sen.ltd/portfolio/prime-factorize/
• 🏢 Company: https://sen.ltd/