I'm trying to solve this problem, and i need to find all primes $p$ for which $ord_p(3)$ is a power of $2$.
If such primes exist then they are of the form $p=2^km+1$ with $k\geq1$ and $m$ an odd integer, because $ord_p(3)$ is a power of $2$ we can assert that $p+1\leq 3^{2^k}$ which affirms that there is no such primes if $3^{2^k}\leq p$, numerically I find only fermat primes.
Question Can we find all odd primes $p$ such that $ard_p(3)$ is a power of $2$
Primes $p$ with the property that $\operatorname{ord}_p(3)=2^k$ are surely factors of the number $$ N_k:=3^{2^k}-1. $$ Furthermore, if an odd prime $p\mid N_k$, then the order of $3$ modulo $p$ is always a power of two (as the order must be a factor of $2^k$).
On the other hand $$ N_{k+1}=3^{2^{k+1}}-1=(3^{2^k}-1)(3^{2^k}+1)=N_k(N_k+2). $$ Clearly $\gcd(N_k,N_k+2)=2$, so if $p$ is an odd prime factor of $N_k+2$ we can be certain that the order of $3$ modulo $p$ is exactly $2^{k+1}$. Because $N_k$ is not a power of two for any $k>1$ (Catalan's conjecture, now a theorem, implies this immediately, but is probably overkill), we see that for any $k>1$ there exists at least one prime $p$ such that $\operatorname{ord}_p(3)=2^k$. This immediately implies that there are infinitely many primes with this property.
Here's the beginning of the list $$ \begin{array}{c|l} k&\text{primes with $\operatorname{ord}_p(3)=2^k$}\\ \hline 2&5\\ 3&41\\ 4&17,193\\ 5&21523361\\ 6&926510094425921\\ 7&1716841910146256242328924544641\\ 8&257,275201,138424618868737, 926510094425921, 3913786281514524929,153849834853910661121 \end{array} $$
At which point my patience to wait for another factorization runs out. Surprisingly few primes actually. Probably somebody else knows more about this.