Problem
Given a number n, $2 \leq n \leq 2^{63}$. $n$ could be prime itself. Find the a prime $p$ that is closet to $n$.
Using the fact that for all prime $p$, $p > 2$, $p$ is odd and $p$ is of the form $6k + 1$ or $6k + 5$, I wrote a for-loop checking from $n – 1$ to 2 to check if that number is prime. So instead of checking for all numbers I need to check for every odd of the two form $p \equiv 1 \pmod{k}$, and $p \equiv 5 \pmod{k}$. However, I wonder if there is a faster algorithm to solve this problem? i.e. some constraints that can restrict the range of numbers need to be checked? Any idea would be greatly appreciated.
Best Answer
You mention $2^{63}.$ It's known that below $4\cdot10^{18}\approx2^{61.8},$ there is at least one prime every 1476 numbers. So a reasonable algorithm would be to sieve some numbers smaller than n (up to 2000 if you want to be on the safe side) up to some small bound, then check the remaining numbers with the Miller-Rabin test. Test any that pass with a primality-proving algorithm—do not use AKS as other answers have suggested; it is not fast in this range.
Of course 2000 is overkill; an interval of length 200 should be good enough for 99.9997% of cases. But sieving is fast so it's not really obvious what length is optimal. In any case the more important optimization issue is deciding how far to sieve rather than how long of an interval to sieve.
As for the primality-proving algorithm, ECPP works. Recently it was proven that there are no BPSW-pseudoprimes less than $2^{64},$ so a Lucas test following your MR test (to base 2) is even faster.