primitive root producing quadratics

[Pieter Moree]

The polynomial X^2+X+41 is known to every number theorist.
It assumes prime values for X=0,...,39.
This is related to the fact that (-163/q)=-1 (Legendre symbol) for all odd
primes q<=37,
which ensures that Euler's polynomial X^2+X+41 is not divisible by primes
<=37.

Euler's polynomial has a completely overlooked (for all I know) family
member. It is
D. H. Lehmer's polynomial 326X^2+3 (considered by him in 1963). For the
first 206 primes
p assumed by this quadratic form with X>=0, the number 326 is a primitive
root modulo p.
For a random choice of a polynomial and a random g it is very unlikely
that something like
this happens !

What makes Lehmer's polynomial, like Euler's polynomial tick, is that
(-163/q)=-1 for all
odd primes q<=37. This ensures that for these primes q, 326n^2+3 is never
congruent to 1(mod q). Since one easily checks that (326/p)=-1 for primes
of the form 326n^2+3, one infers that either 326 is a primitive root mod p or
the order of 326 mod p is <=(p-1)/41. Since the latter is rather unlikely,
326
has a fair chance of being a primitive root mod p=326n^2+3.

This `explains' the `strange behaviour' that Ireland and Rosen want to be
resolved at p. 47 of their `A classical introduction to modern number
theory'.
(And this was the place were I learned of Lehmer's polynomial.)

The above phenomenon observed by Lehmer (inspired by a 1957 letter
of the mathematical amateur Raymond Griffin), raises the following problems:

Problem 1.
Find f and g such that the analog of the 206 above is as large as possible.

Problem 2.
Take a small fixed number g. Find f such that the analog of the 206 above
is as large
as possible. (The case g=10 is of special interest here.)

Yves Gallot is presently the record holder for Problem 1. He found that
72922 is a primitive root for the first 29083 primes of the form
866416(X+599206)^2+2903975582404049 with X>=0.

No serious computational effort was spent on Problem 2. After a little
effort I got to >=7500 for g=10.

Unlike for prime producing polynomials in this setting one can,
presently at least, achieve some results by modest computing devices.
Given the meagre theoretical knowledge on primes produced by polynomials,
computational results are also of higher relevance than usually in number
theory.
This might make these problems (also) of interest to mathematical amateurs
and
beginning students with a love for computation.

For further details/references the reader is referred to my note:
Primitive root producing quadratics
http://arXiv.org/abs/math/0406033

With pleasure I acknowledge Y. Gallot and P. Tegelaar for their
computational assistence and Andrew Granville for his
theoretical contributions to the paper.
The note was finished during the conference
`Algorithms in Number Theory' at Schloss Dagstuhl; an inspirational
environment !