Fix a constant $a$. Then consider primes $p$ and the sequence
$$a^1-1, a^2-1, a^3-1, a^4-1,...,a^N-1.$$
We say a prime $p$ is a primitive divisor of $a^m-1$ if it divides $a^m-1$ and does not divide $a^j-1$ for $j<m$. Clearly if $N\geq p-1$, then $p$ is primitive divisor of $a^m-1$ for some $m$ in the above sequence. But it is not so clear what more we can say for a particular $p$. I am specifically interested in the partial or full answers to the following question:
For any given $a$, what is the smallest $k$ such that $\exists p<k$ with $p$ a primitive divisor of $a^{2m}-1$ for some $2m<N$?
Alternatively phrased, what is the smallest $p$ with $2|ord(a)$ in $\mathbb{Z}/p\mathbb{Z}$?
I can see some basic results such as that $k\leq a+1$ for any $a$ and $N$ (as $a+1$ is a primitive divisor of $a^2-1$ which is at most prime). Also given certain modular conditions on $a$ we can say $k<a^{1/2}$ via reciprocity (as the smallest quadratic nonresidue mod $a$ will be less than $a^{1/2}$).
Can we do better? Is there known literature on this?