How hard is it to find a prime number with given primitive roots?

Question

Assume that we randomly choose a 100-digit prime number $p$, record which of the first 1000 prime numbers are primitive roots modulo $p$, and then forget about $p$. — How easy or how difficult is it to reconstruct $p$ (or another prime number which has the same primitive roots among the first 1000 prime numbers) from this information?

Answer 1

Giving an algorithm which works unconditionally might be a little hard since we don't even know that $2$ is a primitive root for infinitely many primes. So let me suggest an algorithm which should work in practice in reasonable time (maybe a few days) if you are OK with generating a number $p$ which passes standard probabilistic tests to be prime.

To be precise: you ask a number of different questions, but consider the following problem: one divides the first $1000$ primes into two sets $S$ and $T$ and ask whether one can construct a (big) prime $p$ such that every element in $S$ is a primitive root and every element in $T$ is not. The fact that there is a prime of the order $10^{100}$ which gives such an $S$ and $T$ is not exploited. The prime which is generated by the algorithm on the other hand will expect to have several thousand digits.

An element $(a,p)=1$ is a primitive root modulo $p$ if and only if it is not a perfect $q$th power for every prime $q|p-1$. If $q$ is small, the chance of this happening randomly for every element in $S$ is exceedingly small, and so will certainly not happen randomly. Thus it would be good to restrict to primes $p$ such that $p-1$ has no small factors. It's hard to avoid the factor $q=2$, but there are (conjecturally) infinitely many Sophie Germain primes, and thus equivalently infinitely many primes $p$ for which $p-1$ is twice a prime. For such a $p$, any element is a primitive root if and only if it is a quadratic non-residue which is not $-1 \bmod p$. This suggests the following algorithm:

1. For each prime $q \ne 2$ in $T$, choose a quadratic residue $a_q \bmod q$ with $a_q \not\equiv 1 \bmod q$. If $q=2 \in T$, choose $a_2 = 1 \bmod 8$.

2. For each prime $q \ne 2$ in $S$, choose a quadratic non-residue $a_q \bmod q$. If $q=2 \in S$, choose $a_2 = 5 \bmod 8$.

3. Let $M$ be the product of the first $1000$ primes. Use the Chinese Remainder Theorem to find an integer $a$ which is congruent to $a_q \bmod q$ and $a_2 \bmod 8$ for the first $1000$ primes $q$. If $p \equiv a \bmod 4M$ is prime, then $p \equiv 1 \bmod 4$, and so $(q/p) = (p/q)$ by quadratic reciprocity. It follows that any prime in $S$ is not a quadratic residue modulo $p$ and any prime in $T$ is a quadratic residue modulo $p$. (Taking care of what quadratic reciprocity says for $q = 2$.)

4. Note that $4M = e^{7813.669\ldots}$. Start randomly choosing elements $p$ which are $a \bmod 4M$. By the prime number theorem, the chance that a random element of this size is prime is of the order $1/\log(4M) \sim 1/7183$. However, we know that $p$ is co-prime to the first $1000$ primes by construction, this improves the odds considerably by a factor of order something like:

$$\prod_{n=1}^{1000} \left(1 - \frac{1}{p_n}\right)^{-1} \sim 16,$$

so we should expect to find a prime on roughly one out of every $500$ attempts. Note that for numbers of this size we have good probabalistic algorithms to determine whether $p$ is prime or not. So we can expect to find plenty of primes $p$ of this form.

5. Theses number $p-1$ has no prime factors in the first $1000$ primes except $2$. Hope that the factors $q | p-1$ are large enough that the elements in $S$ are not randomly $q$th powers. The chance of this for a prime $q$ is of the order of

$$(1-1/q)^S,$$

so if $|S| =500$ say, and $q$ is not too small, this is very unlikely to happen.

Here is an example. Choose the set $T$ to consist of primes which are $2$ or $1 \bmod 4$, and the set $S$ to consist of primes which are $3 \bmod 4$. The only reason to choose this set is to make the selection of the $a_q$ easier to write down explicitly, namely take $a_q = -1 \bmod q$ for all $q > 2$ and $a_2 = 1 \bmod 8$. In this way there is an easy choice

$$a = M-1.$$

Now looking for random primes of the form $a + 4Mk = M(1+4k)- 1$, one finds a possible prime for $k=79$. Let

$$p_{79} = 317 \cdot M - 1 = 215\ldots 689,$$

with $p_{79} \sim 2 \times 10^{3395}$. One can check that $p_{79}-1$ has no prime factors (besides $2$) below $10^{10}$. Hence there are at most $339$ more such factors.

Hence a reasonable upper estimate of the probability that the $504$ elements in $S$ are not $q$th powers for each of the remaining factors is something like:

$$ \left(1 - \frac{1}{10^{10}}\right)^{339 \cdot 504} = 0.9999829 \ldots $$

If this isn't good enough for you and you want a $p$ that works with probability $1$ (up to all random primality tets), one can thin the search to find primes $p = a \bmod 4M$ which are part of a pair of Sophie Germain-type primes, that is, $(p-1)$ is a power of $2$ times a prime. Here the probability that $(p-1)$ divided by the corresponding factor of $2$ is prime increases again by the same factor of $1/500$ or so (since $p-1$ like $p$ has no factors in the first $1000$ primes except $2$), so now instead of checking the primality of $500$ or so numbers you need to check $500^2 = 250000$ or so before finding one randomly. This is within the realm of possibility if you really wanted to do so.

Update: I left mathematica running to look for Sophie Germain type primes and when I just looked again now it had found one. If $k = 119116$, then

$$p = 476465 \left(\prod_{n=1}^{\infty} p_n\right) - 1 = 323343\ldots800049,$$

is prime and

$$q = \frac{p-1}{16} = 202089\ldots050003$$

is also prime. So $p$ is a prime with exactly the given primitive roots within the first $1000$ primes. (Again, here $p$ and $q$ are verified to be prime only using a pseudoprimality test. These might be within the range of being certifiably proved to be prime, I'm not sure.)

Summary: It is feasible to find a prime $p$ with given primitive roots and non-primitive roots among the first $1000$ primes.

I certainly don't think it is practical to find the original prime: for comparison, if you knew whether $p$ was a quadratic residue or not modulo the first $1000$ primes, that would restrict $p$ to a set of primes of density $2^{-1000}$ which would certainly determine $p$, but not in any useful way: that set is a union of $1/2 \prod_{n=2}^{1000}\left(\frac{p-1}{2}\right)^2$ arithmetic progressions modulo $4 \prod_{n=1}^{1000} p_n$ and you have no way of knowing how to restrict your $p$ to the any of the absolutely huge number of progressions. The idea for this answer is that if you just need to find a single $p$ you can randomly choose any such progression, and then additionally look for Sophie Germain type primes for which being a primitive root is the same as not being $-1$ nor a quadratic residue.