Mathematical Principles & Theorems
Investigates computational number theory algorithms: (1) Miller-Rabin probabilistic primality test: For odd \(n-1 = 2^s d\), tests witnesses \(a\) satisfying \(a^d \not\equiv 1 \pmod n\) and \(a^{2^r d} \not\equiv -1 \pmod n\) for \(r \in [0, s-1]\) (error probability \(< 4^{-k}\)); (2) Pollard's rho integer factorization: pseudo-random walk \(x_{k+1} = (x_k^2 + c) \bmod n\) finding cycles with Floyd's algorithm in expected \(\mathcal{O}(n^{1/4})\) time; (3) Prime Number Theorem: \(\pi(x) \sim \frac{x}{\ln x}\).
Operating Instructions
- Enter any positive integer \(N\) into the numeric input box.
- Click Test Primality to run deterministic or Miller-Rabin tests with witness certificates.
- Click Factorize to decompose \(N\) into its unique prime power factors \(\prod p_i^{a_i}\).
- Examine prime counting function \(\pi(x)\) plots and prime gap distribution histograms.