Sometimes we need some prime number with certain minimum size for modular algorithm.

For practical purposes we can precompute (using fast randomized algorithms) table of some primes for range which makes sense in application.

However I'm interested how fast theoretically (in terms of time complexity on $n$) we can find some prime with at least $n$ bits? It shouldn't be random, just any prime which we deterministically can find.

Just checking all numbers above $2^n$ with AKS test will do the job, but I feel better can be done, but using numbers of specific form, for which fast deterministic test is known.


1 Answer 1


In practice, you should absolutely use a randomized algorithm. There is no reason in practice to use a deterministic algorithm, or to care about the complexity of deterministic algorithms.

So I will assume that you are asking only out of theoretical interest. In that case, a reasonable approach is to start with the minimum number $m$, and then search over $m+1,m+2,m+3,\cdots$ until you find the first prime number, using a deterministic primality test. If you are willing to make certain number-theoretic conjectures (e.g., Cramer's conjecture, generalized Riemann hypothesis), then this runs in $O((\log m)^6)$ time (ignoring log log factors), as you only need to explore $O((\log m)^2)$ many values until you find the first prime, and you can test for primality using the deterministic Miller's test in $O((\log m)^4)$ time per test.

If you're not willing to make any number-theoretic conjectures, and you want a deterministic algorithm with provable worst-case running time, I'm not aware of any result that proves the problem can be solved in polynomial time (i.e., polynomial in $\log m$).

Again, I emphasize that if you actually want to implement this, don't use any of those deterministic algorithms. Instead, use a randomized primality test.

  • $\begingroup$ As I stated in my question, I am interested in theoretic result. Also AKS test is polynomial unconditionally, but has big power and constant. $\endgroup$
    – Somnium
    Oct 3, 2022 at 8:33
  • 2
    $\begingroup$ @Somnium, I understand. I've given you the fastest algorithm I am aware of, within your constraints -- and as a bonus, it is faster than using the AKS algorithm in the obvious way. $\endgroup$
    – D.W.
    Oct 3, 2022 at 22:01
  • $\begingroup$ Are there any "proven prime" tests that have very different execution times for different primes close together? So if I want any prime, I could test whether p is prime, and if it takes too long, I test a probable prime q hoping that the test runs faster? $\endgroup$
    – gnasher729
    Nov 2, 2022 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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