-1

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

J. W. Tanner
  • 60,406
boxcut
  • 1
  • The numbers are quite small...trial and error shouldn't be too bad. Alternatively, you could set out to compute the order of $5\pmod {23}$. That gets you the desired result very quickly. – lulu Apr 29 '20 at 19:25
  • I cannot brute force so I need to do the other method. how do I computer the order of 5mod 23? – boxcut Apr 29 '20 at 19:30
  • Welcome to Mathematics Stack Exchange. Note that $22\equiv-1\bmod23$ – J. W. Tanner Apr 29 '20 at 19:32
  • What are the possible orders of any element $\pmod {23}$? – lulu Apr 29 '20 at 19:32
  • I should say, however, that there is no reason at all not to use brute force. It happens that this particular problem can easily be solved, but that wouldn't be the case for, say, $3\equiv 5^a\pmod {23}$. – lulu Apr 29 '20 at 19:34
  • unfortunately, it is the requirement of the question to not brute for or use an inefficient algorithm. I'm still unsure what you mean by the order of any element (mod 23) are you saying to compute 5^x from 0 till n till I find an answer? I assume that's brute force though. please clarify and sorry for not understanding – boxcut Apr 29 '20 at 19:39
  • Do you know what the order of $g \mod n$ means? – lulu Apr 29 '20 at 19:41

1 Answers1

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$.

J. W. Tanner
  • 60,406