prime-number-theory

A compact number-theory toolkit for Node. Deterministic primality testing, an Eratosthenes sieve, integer factorization (trial division + Pollard's rho), Euler's totient, gcd/lcm and modular exponentiation.

CommonJS, no dependencies. Uses BigInt where it matters, so 64-bit and larger inputs behave correctly.

Install

npm install prime-number-theory

Example

const nt = require("prime-number-theory");

nt.isPrime(2n ** 61n - 1n);   // true  (Mersenne prime M61)
nt.factorize(360);            // [2n, 2n, 2n, 3n, 3n, 5n]
nt.totient(10);               // 4n
nt.nthPrime(99);              // 541  (the 100th prime, 0-indexed)
nt.modPow(2, 10, 1000);       // 24n

Functions

• isPrime(n) — deterministic Miller-Rabin with a fixed witness set valid well beyond 64-bit. Returns a boolean.
• sieve(limit) — all primes <= limit as an array of Numbers.
• nthPrime(i) — the i-th prime, zero-indexed.
• factorize(n) — sorted list of prime factors with multiplicity (BigInt).
• totient(n) — Euler's totient function.
• gcd(a, b) / lcm(a, b) — greatest common divisor / least common multiple.
• modPow(base, exp, mod) — (base ** exp) % mod by repeated squaring.

Most functions accept either Number or BigInt and return BigInt (the sieve returns Numbers, since its bound is a Number anyway).

Determinism note

The Miller-Rabin witness set {2, 3, 5, ..., 37} is a proven deterministic certificate for all n < 3.317 * 10^24. Above that the test is still a very strong probable-prime check but is no longer a proof.

License

ISC