Polynomial strategy

The polynomial strategy is a strategy to obtain a good algorithm for the finding primes project by means of computing certain polynomials in various rings that detect primes.

The basic ideas are as follows.

I. First, observe that to find a prime quickly, it would suffice to have an algorithm which, when given an interval [a,b] as input, determines whether that interval contains at least one prime. Indeed, once one has that algorithm, one can find a prime by starting with a large interval (e.g. [math]\displaystyle{ [10^k, 2 \times 10^k] }[/math]) that is already known to contain a prime (by Bertrand's postulate), and then reduce that interval to a single prime by a binary search using only O(k) steps.

II. Now fix [a,b], with a, b both of size O(N) (say), and consider the polynomial [math]\displaystyle{ f \in F_2[x] }[/math] defined by

[math]\displaystyle{ f(x) := \sum_{a \leq p \leq b} x^p \hbox{ mod } 2 }[/math]

where p ranges over primes. Clearly, this polynomial is non-zero iff [a,b] is a prime. So it will suffice to have an efficient algorithm (the benchmark time to beat here is [math]\displaystyle{ O(N^{1/2+o(1)}) }[/math]) which would detect whether f is non-zero quickly. (The reason for working modulo 2 will be made clearer in the next step.)

III. The reason we work modulo 2 is that f has a number of nice forms to exploit. In particular, note that for a given number n, the number of divisors between 1 and n is odd if n is prime, and even if n is composite and non-square. So, we morally have

[math]\displaystyle{ f(x) = \sum_{a \leq n \leq b} \sum_{1 \leq d \lt \sqrt{n}: d | n} x^d \hbox{ mod } 2 }[/math]

except for an error supported on square monomials [math]\displaystyle{ x^{m^2} }[/math] which hopefully can be compensated for later.

TO BE CONTINUED...