Mathematics – Number Theory
Scientific paper
2010-09-20
Mathematics
Number Theory
15 pages, no figures, to appear, Math. Comp.. This paper was the outcome of the online collaborative mathematics project Polym
Scientific paper
Given a large positive integer $N$, how quickly can one construct a prime number larger than $N$ (or between $N$ and 2N)? Using probabilistic methods, one can obtain a prime number in time at most $\log^{O(1)} N$ with high probability by selecting numbers between $N$ and 2N at random and testing each one in turn for primality until a prime is discovered. However, if one seeks a deterministic method, then the problem is much more difficult, unless one assumes some unproven conjectures in number theory; brute force methods give a $O(N^{1+o(1)})$ algorithm, and the best unconditional algorithm, due to Odlyzko, has a run time of $O(N^{1/2 + o(1)})$. In this paper we discuss an approach that may improve upon the $O(N^{1/2+o(1)})$ bound, by suggesting a strategy to determine in time $O(N^{1/2-c})$ for some $c>0$ whether a given interval in $[N,2N]$ contains a prime. While this strategy has not been fully implemented, it can be used to establish partial results, such as being able to determine the \emph{parity} of the number of primes in a given interval in $[N,2N]$ in time $O(N^{1/2-c})$.
Polymath D. H. J.
No associations
LandOfFree
Deterministic methods to find primes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Deterministic methods to find primes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic methods to find primes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-696579