Number-Theory Lab

How it works

Big-integer number theory with the working shown: Miller–Rabin primality (deterministic up to 3.3·10^24, otherwise with a stated number of rounds), factorisation by trial division and Pollard rho, gcd/lcm with the extended Euclidean table, modular inverse and exponentiation, the Chinese remainder theorem, Euler φ and divisors, prime counting up to 10 million, Collatz sequences and continued fractions.

• Primality: trial division by primes below 100, then Miller–Rabin. Below 3,317,044,064,679,887,385,961,981 the first 13 primes as bases form a proof (Sorenson & Webster 2015), which covers every 64-bit number. Above it, the stated number of rounds uses bases derived from SHA-256 of n (reproducible); a composite passes each round with probability at most 1/4.
• Factorisation: trial division up to 10,000, then Pollard–Brent rho with a fixed iteration budget; factors are checked with Miller–Rabin. If the budget runs out the remaining cofactor is reported as unfactored, never guessed.
• φ(n) = ∏ p^(e−1)(p − 1), σ(n) = ∏ (p^(e+1) − 1)/(p − 1), d(n) = ∏ (e + 1). Carmichael numbers are detected with Korselt's criterion (square-free, composite, p − 1 | n − 1 for every prime factor).
• gcd via the Euclidean algorithm with Bézout coefficients; inverse exists iff gcd(a, m) = 1. CRT merges congruences pairwise and also handles non-coprime moduli (or reports that none exists). π(n) uses an odd-only sieve of Eratosthenes.

Sources

• Sorenson, J.; Webster, J. (2015): Strong pseudoprimes to twelve prime bases (Mathematics of Computation)
• Brent, R. P. (1980): An improved Monte Carlo factorization algorithm (BIT 20)