9

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.

J. M. ain't a mathematician
  • 75,051
roxrook
  • 12,081
  • 4
    Use a strong probabilistic test and then verify primality with a deterministic test, e.g. see http://primes.utm.edu/prove/index.html – Bill Dubuque Apr 27 '11 at 00:38
  • 3
    Would storing all the primes within the range to some array and using (a suitably modified) binary search be impractical? – J. M. ain't a mathematician Apr 27 '11 at 00:40
  • @J.M: I thought of that method but let's assume we don't know all primes at hand. – roxrook Apr 27 '11 at 00:43
  • @Bill Dubuque: Very nice link! Many thanks Bill ;) – roxrook Apr 27 '11 at 00:44
  • @JM: Then you'd have to know all the primes already. I suppose this isn't too bad, as $2^63$ has only 19 digits. But if can assume we have a list of the first $10^18$ or so primes, this would certainly work quickly. – davidlowryduda Apr 27 '11 at 00:46
  • You gave a range for $n$; you should be able to sieve accordingly to generate all the primes within the range... – J. M. ain't a mathematician Apr 27 '11 at 00:46
  • @J.M: Sieve! Thanks for that idea. Although I love the idea of storing array, I still prefer an approximation on range. – roxrook Apr 27 '11 at 00:49
  • 1
    Is it $2^{63}$ right? not $2^63$? A typo? – roxrook Apr 27 '11 at 00:50
  • @lhf: Ah, then Chan should use a combination of Bill's suggestion and my suggestion, then. It's certainly quicker to search an array than to do Miller-Rabin or somesuch compositeness test... – J. M. ain't a mathematician Apr 27 '11 at 00:53
  • 7
    You only have to check the interval $[n/2,2n]$ because of Bertrand's postulate. – lhf Apr 27 '11 at 00:53
  • @lhf: Very nice one :). Great thanks! – roxrook Apr 27 '11 at 00:55
  • @lhf: In fact, you probably only have to check an interval of length $O(\log n)$. – Yuval Filmus Apr 27 '11 at 01:03
  • 3
    @Yuval: I presume you're appealing to the prime number theorem? You have to be a little careful with that. It is known that the lim sup of the gaps between subsequent prime numbers is superlogarithmic. http://en.wikipedia.org/wiki/Cram%C3%A9r's_conjecture – cong Apr 27 '11 at 01:11
  • 1
    Also asked here: http://stackoverflow.com/questions/5798060/what-is-the-most-efficient-algorithm-to-find-the-closet-prime-less-than-a-given-n. Why ask at multiple places? – Aryabhata Apr 27 '11 at 01:12
  • 1
    possible duplicate (Variant) of The least prime greater than 2000. Charles' answer should apply here too. – Aryabhata Apr 27 '11 at 01:14
  • @Moron: In my opinion, this is a more theoretical place, where stackoverflow is more practical. For example, bitwise could be a big factor on improving algorithm with numbers which I don't expect to find here. I was expecting a theoretical approach here, while a practical implementation there. – roxrook Apr 27 '11 at 01:44
  • @Cong: I was under the impression that some GRH implies something similar. For the record, Cramér's conjecture implies an interval of size $O(\log^2 n)$. – Yuval Filmus Apr 27 '11 at 02:03
  • 4
    @Chan: You will just be wasting a lot of people's time by asking in multiple places. If you are looking for different solutions you should mention that in your question. Also, disagree that you won't find good practical answers here. IMO, you will find much better answers (if needed, using 'bitwise') here than on stackoverflow. – Aryabhata Apr 27 '11 at 02:05
  • @Yuval: My bad! I forgot to mention the result I was referring to. I meant the result by Westzynthius stated under the section "Proven results on prime gaps". – cong Apr 27 '11 at 02:28
  • @Moron: If you could point how asking multiple places is wasting people's time, I would agree with you. Otherwise, I refuse this suggestion. To me, there are two different sets of users, here and stackoverflow. At stackoverflow, there are much more experienced programmer who I believe would have a deeper understanding on operations of computer. For example, the IEEE standard, from a mathematical point of view, I wouldn't care about how this number are interpreted. But from a programming background, I do care. Applied maths and computer science should be separate subjects, shouldn't they? – roxrook Apr 27 '11 at 02:33
  • @Moron: On the other hand, by practical I meant the use of computer architect, not the idea is not practical. I apologize for my poor interpretation. – roxrook Apr 27 '11 at 02:37
  • 3
    @Chan: The 'computer architecture' optimizations you speak of, are considered 'micro optimizations' which are to be done only after you have an algorithm, have the code, have profiled the code and then pin pointed areas needed for optimization. What you have here is just an ask for an algorithm. Unless you have the code the answers on stackoverflow will pretty much mimic the answers here (and showing the code would be off topic here). You are wasting the time of people, especially more so, when the question statement is exactly the same. – Aryabhata Apr 27 '11 at 02:50
  • ... If there is a question which is on-topic on two sites it is in bad form to ask on both. Just because the audience have possibly different set of expertise does not mean you will get a different set of answers. For instance, consider the answers you got at both places so far (and the answers in the dupe post in my comment above). Anyway, you are free ignore whatever I said... – Aryabhata Apr 27 '11 at 02:57
  • @Moron: I believe different expertises could give different answers because they look at the problem from different angles with different knowledges. However, you were right about I shouldn't post the exact same question. I will take this. I often don't ignore people's suggestion unless they talk in a very unconstructive way. Thank you. – roxrook Apr 27 '11 at 03:14
  • 5
    I think it's OK to ask (essentially) the same question in two venues, $\bf\ as\ long\ as\ you're\ upfront\ about\ it$, that is, as long as in each venue you note that you're asking it in the other, and you give a link so people can easily check to see that they are not duplicating effort. – Gerry Myerson Apr 27 '11 at 05:14
  • 2
    @J.M.: No, it's not practical. There are O(n/log n) primes less than n, each with up to O(log(n)) bits, for a total storage requirement of O(n) bits. 2^63 is an unreasonable number of bits to store. – wnoise Apr 27 '11 at 20:05
  • @wnoise: I see now, thanks. So, just store the first few primes so that one can do binary search, and then use a compositeness test thereafter... – J. M. ain't a mathematician Apr 27 '11 at 23:50
  • Define "most efficient." Do you refer to the asymptotic time complexity of the algorithm as the input gets arbitrarily large? For practical usage, keep in mind the following quote: "Fancy algorithms are slow when $n$ is small, and $n$ is usually small. Fancy algorithms have big constants. Until you know that $n$ is frequently going to be big, don't get fancy." —Rob Pike – Wildcard Jan 04 '17 at 02:23

3 Answers3

8

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.

Charles
  • 32,122
  • using a segmented seive upto root of n would be a good optimization . – saruftw Jun 11 '16 at 10:45
  • @saru95 I don't think so, not at that size. Faster to sieve out the easy composites and test the rest rather than doing billions of divisions. – Charles Jun 11 '16 at 14:37
5

This is an extension of Bill's comment.

It is certainly reasonable to use strong probabilistic tests and then verify with the AKS algorithm. In fact, if we look for primes alternately above and below the target number and test with AKS, where each primality test takes time at most $\log^{O(1)}N$, and there is an approximately $\dfrac{1}{\log N}$ chance that each is prime, one would be at least 99% sure to find a prime in time $O(\log^{O(1)}N)$. But this is not deterministic - conceivably, there exists an interval where this works very poorly, far worse than logarithmic time. To be fair, I suspect such an interval does not exist in the numbers up to $2^{64}$. But speaking generally, a deterministic algorithm might be desired.

To that end, I refer you to the results of Polymath4 "Finding Primes," a collaborative mathematical experience that sought to find a method to deterministically find primes of about a given size. In their paper, they describe deterministic methods that take time $O(N^{.5 + \epsilon})$, which I think is pretty exciting.

Ultimately, I would say that Bill's suggestion of probabilistically checking numbers and then verifying their primality is optimal. But the promise of a deterministic algorithm is... quite alluring, I think, too.

Gaurang Tandon
  • 6,449
davidlowryduda
  • 91,687
  • 1
    Just a note: The gain by using probabilistic primality test is that if a number is deemed composite, we can ignore running the deterministic test on it, as usually probablisitic tests don't lie about compositeness. – Aryabhata Apr 27 '11 at 02:18
  • This is very clear! Whenever I find primes of a large size, I always just search using Miller-Rabin and AKS. But it is still probabilistic, not deterministic. – davidlowryduda Apr 27 '11 at 02:31
  • 1
    @mixed: Most probabilistic tests guarantee compositeness (I believe Miller-Rabin is one of those). So using Miller-Rabin then AKS is a deterministic algorithm! – Aryabhata Apr 27 '11 at 02:55
  • @Moron: The problem with your statement is that its runtime cannot be calculated deterministically. We say it's probabilistic in time $O(log^{O(1)}$ because we expect it to run about this speed. But as there are arbitrarily long strings of integers that are composite, there necessarily exist arbitrarily bad-case scenarios for this probabilistic algorithm. So its deterministic running time is terrible - much worse than simply performing a sieve (in fact, arbitrarily bad if no limit is placed on n). – davidlowryduda Apr 27 '11 at 02:59
  • 1
    @mixed: There are many determinstic algorithms whose runtime is not known precisely. Shell Sort is one classic example. Deterministic does not mean you know the runtime. It just means you are 100% confident of the output. The whole point of using a probabilistic test is that we will likely move over the composites quickly and only run AKS on some composites and primes saving a lot of computation time. – Aryabhata Apr 27 '11 at 03:05
  • @Moron: Again, I don't disagree. But here, we are looking for the fastest algorithm to find a prime next to some number, and to use probabilistic methods does not give a certain runtime. The paper I referenced does, and for large enough N (above what the OP considers, I think) it runs faster than the probabilistic methods to achieve a deterministic algorithm. To be short, if we want certainty, it's faster. It's unfair to give it's probabilistic runtime for a non-deterministic result. – davidlowryduda Apr 27 '11 at 03:09
  • @Moron: I want to make myself clear- I understand the advantages of the probabilistic algorithm. But if we are speaking of deterministic results, then that algorithm is only better on average. – davidlowryduda Apr 27 '11 at 03:10
  • @mixed: If you want to find the next prime $p$ greater (or less than) a given number $n$, then running AKS sequentially till you hit one will be slower than running probabilistic test (except possibly a few cases). Just because you cannot determine the runtime does not mean it cannot be the faster than an algorithm whose runtime you do know. Miller-Rabin+AKS is a determinsitic algorithm with deterministic results (not runtime of course). Anyway, I guess we are just talking about definitions... – Aryabhata Apr 27 '11 at 03:12
  • @Moron: The deterministic algorithm I reference is NOT the AKS! That is a terrible, also probabilistic algorithm. I refer you again to the paper, http://arxiv.org/PS_cache/arxiv/pdf/1009/1009.3956v3.pdf, for the deterministic algorithm I am championing. I note that nowhere does it use AKS. I also note that running the AKS sequentially also has arbitrarily poor runtime for the exact reasons I mentioned in my first comment directed at you above (and this was the object of that comment). – davidlowryduda Apr 27 '11 at 03:15
  • 1
    @mixed: Come on. You know very well it does not matter if it was AKS or not :-) Anyway, I agree that it is not determinstic with respect to the runtime, but it is determinstic with respect to the output. We are talking of different things I suppose. Anyway... – Aryabhata Apr 27 '11 at 03:22
  • @Moron: Indeed, so it goes. Until next time! ;p – davidlowryduda Apr 27 '11 at 03:26
  • Since the question was restricted to 63-bit inputs, BPSW is deterministic and 5+ orders of magnitude faster than AKS. So no need for all the complication -- just use a wheel to skip trivial composites and run BPSW on the others until it returns true. Replace BPSW with the 7-base deterministic M-R test if you'd prefer to sacrifice some speed to avoid writing a Lucas test (which will still be 100,000 times faster than AKS). – DanaJ May 26 '15 at 18:36
  • @mixedmath, you write "Whenever I find primes of a large size, I always just search using Miller-Rabin and AKS." Could I ask what "large" is, and what AKS implementation you use? I'm not aware of any that are practical beyond, say, 100 digits. All are horrendously slow compared to APR-CL or ECPP (or even BLS75 for < 80 digits). – DanaJ May 26 '15 at 18:50
3

Use sieving to optimize your loop even more.

Guess an interval of reasonable length on which your prime is going to be found. Initialize a corresponding table with entries all equal to "true".

Go over a list of small primes $p_i$, and compute $n \mod p_i$. Using that value, you can mark off some of the entries in the table as "false".

Now do what Bill suggests - go over the remaining entries, use Miller-Rabin and then if you want to be really sure, some deterministic test (not necessarily AKS, which is slow).

Yuval Filmus
  • 57,157