Odd. There is an article about this in the October M.A.A. Monthly, pages 737-742, by R. Thangadurai and A. Vatwani.  They give an elementary argument to show 
$$  p \leq 2^{\phi(q) + 1} - 1.$$ The best unconditional result they report is T. Xylouris (2009),
$$  p \leq c_1 q^{5.2}$$ which improves a 1992 result of Heath-Brown.

Apparently Oesterle showed that GRH implies 
$$ p \leq 70 q (\log q)^2    $$ which is much better.