2
$\begingroup$

Consider receiving as input $x\in\mathbb N$ and computing some (any) prime $p\in[x,2x]$.

What is the complexity of the above problem?


A natural way to approach this problem is to generate random integers in $x,\ldots,2x$ and check for their primality using Miller-Rabin or a deterministic algorithm such as AKS.

However, this may be suboptimal. What is the best-known runtime for the problem?

$\endgroup$
2
$\begingroup$

You can speed up this algorithm somewhat by generating a random integer which is coprime to all small primes. This can be done efficiently using a sieve: pick an appropriately sized random interval inside $[x,2x]$, and cross off all integers in the interval which are multiples of small primes (you can do this efficiently by finding the first multiple of a given prime, and then iterating over the remaining multiplies). Now use your favorite algorithm to find a prime within the integers not ruled out. The size of the interval should be chosen so that it guarantees that there is a prime (so about $\log x$ or somewhat larger).

$\endgroup$
  • $\begingroup$ Thanks. Am I correct to assume that this does not result in an asymptotical improvement? Or can we set the sieve cleverly to achieve that? $\endgroup$ – R B Dec 25 '17 at 16:21
  • $\begingroup$ Since you mentioned the AKS algorithm, I assumed you're not interested in efficient algorithms. $\endgroup$ – Yuval Filmus Dec 25 '17 at 16:23
  • $\begingroup$ It probably does result in an asymptotic improvement, since the sieving part is very fast, and it drastically improves your success probability. To know for sure, you'll have to do the calculation. $\endgroup$ – Yuval Filmus Dec 25 '17 at 16:24
  • $\begingroup$ I also mentioned MR, which is probably the fastest option :). $\endgroup$ – R B Dec 25 '17 at 16:25
  • 1
    $\begingroup$ I would guess that sieving buys you a superconstant speed-up. Finding an a priori denser area sounds very difficult. $\endgroup$ – Yuval Filmus Dec 27 '17 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.