Smallest witness for checking the primality of a number In this link < it is stated that the smallest witness for a composite number is always less than $2ln(n)^2$ , assuming the extended Riemann-hypothesis. > Is there a known bound for a witness without making unproven asumptions ?

For short, the answer is _yes, but it is unbelievably weaker_.

In particular, it changes the expected complexity from "polynomial" to "exponential".

* * *

Now, the long answer: by combining the Burgess' inequality with the Vinogradov's amplification trick (based on the Dickman function) it is possible to prove that $\eta_p$, the least quadratic non-residue $\\!\\!\pmod{p}$, is:

$$ \ll p^{\frac{1}{4\sqrt{e}}} $$ that is roughly $p^{\frac{1}{7}}$. Similar unconditional bounds are known for the least generator $\\!\\!\pmod{p}$.

On the other hand, an unconditional result of Montgomery (that is an elegant improvement of a previous result of Chowla) shows that for an infinite number of primes, $$\eta_p \gg \log(p)\log\log\log(p)$$ holds.