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.

  • $\begingroup$ 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 :-) $\endgroup$ – Jyrki Lahtonen May 8 '17 at 8:48

The number $p=257$ is very special, because

  • it is a prime, and
  • $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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.