Upper bounds on the order of a number in prime fields Let $k$ be a fixed integer and for any prime number $p$ larger than $k$, let $\text{Order}(k,p)$ be the order of $k$ in $\mathbb{F}_p$ (i.e., $\text{Order}(k,p)$ is the least integer $n$ such that $k^n \equiv 1 \bmod{p}$).

Question. Give an upper bound to the sequence  $$v_n=\inf_{t>n}\left(\text{Order}(k,p_t)\right),$$  where the $p_t$'s
  are the enumeration of all prime numbers in increasing order.

Fermat's little theorem provides the bound $v_n\leq p_n - 1$. Can a bound of $p_n^\epsilon$ be shown, for any $\epsilon>0$?  Experiments suggest a bound of $\log(p_n)$.
 A: This is not an answer, but maybe it's useful.
For example, take $k=2$.  If $2^q-1$ is a Mersenne prime, it is $p_m$ where $q \sim \log_2 m$.  Of course $\text{Order}(2, 2^q-1) = q$, 
so $v_n \le q$ if $n \le m$.  If there are infinitely many Mersenne primes we will have $$\liminf_{n \to \infty} \frac{v_n}{\log_2(n)} \le 1$$
A: Rephrasing, you are calling $ v_n $ the smallest integer $m$ such that $ k^m - 1$  has a prime factor not among the first $n$ enumerated primes.
If you have the standard numbering (primes in increasing order), then $v_n$ is going to look like  $m$ or less right up until you hit the largest prime factor of $k^m - 1$, which presumably is larger than any prime factor of the same form for smaller values of $m$.  Since these primes are often large, this accords with your observed values. This is because prime factors of $k^m - 1$ as $m$ varies are often larger than a fixed power (expect at least one of them to be larger than $k^{m/2} -1$).
However, let's pretend you pick the unluckiest enumeration, so that the first n primes are the factors of the first m numbers of the form $k^m - 1$.  Zsigmondy says that for each m, a new prime appears as a factor of  $k^m-1$ (unless m=6 and k=2). So $v_n$ will eventually be less than $n$, and conjecturally less than $n/log n$, even if you are unlucky.
Gerhard "The Fortunes Of Number Theory" Paseman, 2019.04.05.
