A Self-Contained Next-Prime Engine: Efficient Computation of Successive Primes

This working paper presents NextPrime, a self-contained algorithm for computing the next prime after a given prime ( p ). The method uses a 6k±1 wheel factorization and deterministic Miller-Rabin primality testing, ensuring correctness for 64-bit integers. We provide a formal correctness proof, analyze time complexity (worst-case O(p⋅(log⁡p)3)O(p \cdot (\log p)^3)O(p \cdot (\log p)^3) , expected O((log⁡p)4)O((\log p)^4)O((\log p)^4) ), and validate performance with unit tests up to the 100,000th prime and benchmarks around p=106p = 10^6p = 10^6 (0.5–1 μs per call). The implementation is included as a supplementary Python module. This work is relevant for applications in cryptography and computational number theory.