This is a sequel to this MO question: 


[The multiplicative order of 2 modulo primes](https://mathoverflow.net/questions/60441/the-multiplicative-order-of-2-modulo-primes)


As shown in Charles Matthews' paper linked to there, it is not hard to show that for each $\delta > 0$ there is a $c = c(\delta) > 0$ such that the set of primes $p$ for which the multiplicative order $n\_p := \mathrm{ord}\_p(2)$ of $2$ modulo $p$ satisfies $n\_p < c\sqrt{p}$, has density $< \delta$. In particular, the set of primes with $n\_p < p^{\frac{1}{2} - \epsilon}$ have zero density.


My question is, is $1/2$ *really* the critical exponent? For $\epsilon > 0$, is there a positive density of primes $p$ with $n\_p < p^{\frac{1}{2} + \epsilon}$. Moreover, is there a $C < \infty$ for which the set of $p$ with $n\_p < C\sqrt{p}$ has positive density?


I would also like to ask about the analogous question for elliptic curves: is $1/3$ *really* the critical exponent there? Given a point $P$ of infinite order, is there a $C < \infty$ for which the set of $p$ such that the order of $P \mod{p}$ is $< C \sqrt[3]{p}$ has positive density?



The critical exponent in the multiplicative order of 2 modulo primes
The Generalized Riemann Hypothesis (for Dedekind zeta functions of certain Kummerian fields) would show that the "critical exponent" for the multiplicative order problem is $1$. In fact, GRH implies that if $g$ is any function tending to infinity, then (asymptotically) 100% of primes $p$ satisfy $n\_p > p/g(p)$. This follows from the methods of Hooley in his conditional solution of Artin's conjecture; an explicit reference is Theorem 23 in this paper of Kurlberg and Pomerance:


<http://www.math.dartmouth.edu/~carlp/PDF/par13.pdf>


I suspect something similar can be said about your 2nd problem assuming GRH for Dedekind zeta functions associated to division fields. There's lots of relevant work in this area by Cojocaru, David, and others. But I'm not so knowledgeable about this, so I'll bow out now.


