[Tonelli–Shanks algorithm][1] needs quadratic nonresidue $n$ modulo prime $p$. If the extended Riemann hypothesis is true, then the first quadratic nonresidue $n_p$ is always less than $3(\log p)^2/2$ (Wedeniwski 2001) for $ p>3$. Under this assumption Tonelli–Shanks algorithm becomes polynomial. Probabilistic heuristics (presuming that each non-square integer has a 50-50 chance of being a quadratic residue) suggests that $n_p$ should have size $O( \log p )$. The best unconditional estimate (Burgess) is $n_p\ll p^\theta$ for any $\theta >1/4\sqrt e$. 

See also extended discussion at [The least quadratic nonresidue, and the square root barrier.][2]


  [1]: https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
  [2]: https://terrytao.wordpress.com/tag/least-quadratic-nonresidue/