18
$\begingroup$

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?

$\endgroup$
5
  • 3
    $\begingroup$ What about just asking whether each of the first 1000 primes $q$ is a quadratic non-residue modulo $p$? It seems that this would happen roughly half the time, so you would get some 1000 bits of useful info. I don't know whether this is enough to reconstruct $p$, but it might be an easier problem. $\endgroup$ Jul 31, 2022 at 20:39
  • 2
    $\begingroup$ @LevBorisov Using quadratic reciprocity and the chinese remainder theorem, it should be straightforward to find a prime $p$ with given quadratic residues and -nonresidues (finding the smallest though may not be easy). In contrast, for primitive roots, I don't see how quadratic reciprocity would help much. $\endgroup$
    – Stefan Kohl
    Jul 31, 2022 at 21:13
  • 1
    $\begingroup$ I don't see it as straightforward. If one just looks at various cases of what you get modulo small primes, then the number of cases seems to be not feasible. In fact, if this could be done, then your original problem would also be manageable, since a reasonable proportion of $q$ would be a generator, hence quadratic non-residue. $\endgroup$ Aug 1, 2022 at 11:43
  • 2
    $\begingroup$ @LevBorisov: Coppersmith method can be employed here, like in mathoverflow.net/q/224033 $\endgroup$ Aug 2, 2022 at 4:30
  • $\begingroup$ @MaxAlekseyev Thank you, interesting method! $\endgroup$ Aug 2, 2022 at 18:20

1 Answer 1

7
$\begingroup$

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.

  1. 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.

$\endgroup$
0

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.