how would I solve $22$ ≡ $5^a$ mod $23$ for $ a$?

Question

I need to solve $22$ ≡ $5^a$ mod $23$ for $a$. I am new to discrete logarithms, and I'm confused how to go about this. I tried using the baby step giant step algorithm approach but I'm still unsure

Answer 1

You're looking for $a$ such that $5^a\equiv-1\bmod23$.

By Fermat's little theorem, $5^{22}\equiv1\bmod23$; that implies $5^{11}\equiv\pm1\bmod23$.

By Euler's criterion, $5^{11}\equiv\left(\dfrac5{23}\right)\bmod23.$

Quadratic reciprocity says $\left(\dfrac5{23}\right)\left(\dfrac{23}5\right)=1$ since $5\equiv1\bmod4$.

Since $3$ is not a quadratic residue modulo $5$, that means $5^{\color{blue}{11}}\equiv-1\bmod23$.