Timeline for How hard is it to find a prime number with given primitive roots?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 2, 2022 at 18:20 | comment | added | Lev Borisov | @MaxAlekseyev Thank you, interesting method! | |
| Aug 2, 2022 at 4:30 | comment | added | Max Alekseyev | @LevBorisov: Coppersmith method can be employed here, like in mathoverflow.net/q/224033 | |
| Aug 2, 2022 at 2:50 | answer | added | user488927 | timeline score: 7 | |
| Aug 1, 2022 at 11:43 | comment | added | Lev Borisov | 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. | |
| Jul 31, 2022 at 21:13 | comment | added | Stefan Kohl♦ | @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. | |
| Jul 31, 2022 at 20:39 | comment | added | Lev Borisov | 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. | |
| Jul 31, 2022 at 20:14 | history | asked | Stefan Kohl♦ | CC BY-SA 4.0 |