# Calculate the order of 3 modulo 257

How on earth would you go about this? I would start with g is a primitive root then g^i congruent to 3 but then I get stuck thereafter.

• I don't think that looking for the discrete logarithm of $3$ is a useful approach. It works in theory, but A) were you given a generator $g$? B) finding the discrete log is time consuming. Except after you have completed this exercise and selected $g$ in a suitable way :-) – Jyrki Lahtonen May 8 '17 at 8:48

The number $p=257$ is very special, because
• $p-1=2^8$ is a power of a prime.
Lagrange's theorem then implies that the order of a non-zero coset modulo $p$ must also be a power of two. More precisely, the order is $2^k$ for some $k=0,1,2,\ldots,8$.
What this means is that all you need to do is repeated squaring. Calculate $3^2=9\pmod {257}$, $3^4=9^2=81\pmod{257}$, $3^8=81^2$ et cetera. If you haven't hit $1$ by the time you reach $3^{128}$ you know that the order is $256$.
If you have covered quadratic residues then you can take the further shortcut of observing that $3$ is not a quadratic residue modulo $257$. Therefore $3$ cannot be an even power of a primitive root $g$. Hence its order must be _____. You do need the law of quadratic reciprocity for this to go as smoothly as described.