Least supersingular prime Given an elliptic curve over the rationals, what can one say about the size of the smallest supersingular prime?
 A: This is surely a very hard question, given that, to the best of my knowledge, the only way we have of producing any supersingular primes goes back to Elkies (even under GRH), and this would lead to the bounds that ACL discussed.
That said, it seems natural to guess that it should be polynomial in the log of the conductor.  Here's one way to see this: Given a prime $p$, there is a finite set of congruence conditions on $A$ and $B$ for which the elliptic curve $E_{A,B}:y^2=x^3+Ax+B$ is supersingular at $p$; in fact, about $p^{-1/2}$ of elliptic curves mod $p$ are supersingular.  Thus, if $E_{A,B}$ is not supersingular for primes $p\leq X$, say, then $A$ and $B$ must sit inside certain congruence classes modulo each $p \leq X$, whence in certain classes modulo $\prod_{p\leq X} p = e^{(1+o(1))X}$.  Once $X\gg \log^{1+\epsilon} N$, these conditions probably determine $A$ and $B$.  Certainly, if $X \gg \log^k N$ for some large $k$, it is almost inconceivable that $A$ and $B$ would not be determined.
This argument is obviously a little wishy-washy, but it does imply a couple of things.  First, it leads to an easy way to construct elliptic curves whose least supersingular prime is of size $\log N$.  Second, it easily leads to statements like a vast majority of elliptic curves have their least supersingular prime bounded by 1000000.  It also strongly suggests that the average least supersingular prime is bounded, but until you rule out the case that the Elkies-Murty bound is sharp, you won't be able to prove this.
A: edit I just saw that I misread the question. I leave my posting here since I hope that it is interesting for you anyway. /edit
I don't know if you are still interested in the answer but I am currently working on exactly this problem. The result I have is explicit and does not depend on any unproven conjecture. It is one chapter of my PhD thesis (which is not finished yet) and details of the proof would probably go beyond the scope of this thread.
My result ist this:
Let $E$ be an elliptic curve over the rationals with $j$-invariant $j_E$ and conductor $N$. Let \begin{align*}B_{j_E} =
\begin{cases}
\left( \frac{\log j_E}{2 \pi}\right)^2 &\mbox{for } j_E>0,\\
\left(\frac{\log |j_E|}{\pi} + 1\right)^2 &\mbox{for } j_E<0\\
\end{cases},\end{align*} $M \in\mathbb{N}$, $q = 4 \text{rad} (6 N)$ and $n= \max (3, M, B_{j_E})$. For better readability we will write $A = \frac54q(n+2\log q)^2$. Then there exists a supersingular prime $p$ of $E$ such that $p \geq n$ and
\begin{align*}\log p \leq 1.7 \cdot 10^{26} A^{13587505A} h^*(j_E).\end{align*}
The "+1" in the definition of $B_{j_E}$ can probably be omitted but it would make one part of the proof more complicated. Since it only affects the result very very slightly I kept it there.
The bound should be the same for number fields of odd degree. It may be possible to get a similar result on number fields with at least one real embedding (since Elkies proved the existance of inifinitely many supersingular primes also for elliptic curves over number fields with at least one real embedding) where the methods have to be adjusted slightly.
A: Étienne Fouvry and Ram Murty gave a lower bound
(On the distribution of supersingular primes. 
Canad. J. Math. 48 (1996), no. 1, 81–104. http://cms.math.ca/cjm/v48/cjm1996v48.0081-0104.pdf)
which is roughly of the form
$\pi_0(x)\gg \log(\log(\log(x)))$.
Under GRH, Elkies and Murty has previously proved a lower bound 
of the form $\pi_0(x)\gg \log(\log(x)))$.
In comparison, the conjectures of Lang-Trotter predict a lower bound of the form $\pi_0(x)\gg \sqrt x /\log(x)$.
