0
$\begingroup$

So we know the order of 3 must be 256 yet this is too big number to calculate by hand (or calculator) so we use the fact that there exists another primitive root, g, such that 3 is congruent to g^i mod 256.

Then we have 3^256 congruent to g^(i*256) mod 257 where i is between 1 and 255.

I am stuck on how to proceed from here, my notes say: "As 256 is a power of 2, order of 3 is 256 if and only if i is odd."

I don't get this statement; surely g^(i*256) is congruent to 1 mod 257 for any power that is divisible by the order of g so 256 therefore shouldn't i be able to take any value?

$\endgroup$
  • 2
    $\begingroup$ $3$ is a quadratic non-residue of $257$ and that's enough in this case ($256$ is a power of $2$) to ensure that it's a primitive root. $\endgroup$ – Lord Shark the Unknown May 6 '17 at 19:43
  • $\begingroup$ The point has nothing to do with $g^{i*256}$. It has to to do with $g^{i}$. If $i$ is even then $3^{128}=g^{128i}\equiv 1$, so $3$ can't have order $256$. $\endgroup$ – Thomas Andrews May 6 '17 at 19:43
  • $\begingroup$ @ThomasAndrews if i was even (e.g. =2) then g^(128*i) would be g^256 which is 1 by defn? $\endgroup$ – MargaretM May 6 '17 at 20:12
0
$\begingroup$

As the comments indicate, $i$ must be odd since $257$ is prime, $257-1=256=2^8$, and the multiplicative order of any element must be a power of $2$. To find the order of $3$ is not so hard even by hand. You find that $3^{16}\equiv -8 \mod 257 $, then $3^{64}\equiv -16\mod 257$ and you are practically done.

$\endgroup$

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.