There is a result by Oesterle, that proves that you can find the first non residue quadratic modulo a prime in no more than $70\log(p)^2$ step assuming the GRH, this result was then improved by Bach who replaced the constant $70$ by $2$. The result of Oesterle was never published and when I asked him why, he told me because the laptop containing the proof was stolen from his car. However I think he exposed his proof to the mathematical community, so it is widely recognized.
Hicham
- 509
- 4
- 5