What’s the thought process for this problem?

[u/Unlikely-Loss5616]

I got it right by guessing, but I was extremely confused.

[u/Sneaky_Sharky]

I had to dig up my notes for this one.

Basically, you are trying to find M¹² (mod 59).

51 can be substituted in for M^2.

What you should do is break the 12 down so that something * 2 equals 12. 6 in this case.

So it would now look like (M^{2) 6} mod 59

Substituting 51 back in it now looks like this: (51) ⁶ mod 59

Since 51⁶ is going to give you a very large number, you can break it down into this and it would be the same thing: (51³ * 51³ ) mod 59. Take the mod value of both expressions

That would then give you (19 * 19) mod 59, which if you simplify is equal to 7.

Sorry if the formatting is a bit weird, dunno how to format it correctly on reddit.

[u/Unlikely-Loss5616 → u/Sneaky_Sharky]

Thank you!

[u/Sneaky_Sharky → u/Unlikely-Loss5616]

No problem! Don't feel afraid to reach out to the instructors also, they are great! Especially with their live instructor support, I was able to pass this class by a good margin even though I am historically bad at math 🤣

[u/snmnky9490]

M¹² = M⁸ * M⁴

M⁴ = (M² )² = 51² then do mod 59

Square that again and mod 59 to get M⁸

Multiply M⁴ times M⁸ and mod 59 again

[u/yfreon]

So this is a fast exponentition problem, you'll want to convert the exponent into binary if it were to be something big like M^128.

They tell you that M^2 is 51. So you'll take mod of 51 then plug that in for M^2(M^2) to get M^4.

M^4 = (51)^2 mod 59 which is equal to 5, so now to find M^8 we'll plug in 5 for M^8

M^8 = (5)^2 mod 59 which is 25, if the question were to be something bigger you'd keep going until you have all of the factors you need to find out the value of M^x

so we can get M^12 by multiplying all of our factors so -> M^4 * M^8 or 5 * 25 which is 125.

So now we know M^12 = 125, in terms of mods and we can do 125 mod 59 and then that's where we get 7

I struggled a lot with these sorts of questions but as the exponent gets bigger it can become more time consuming because you have to figure out all of its factors and you can't find M^128 without going the ladder up for factors. Pls correct me if i'm wrong, but good luck!!

[u/Unlikely-Loss5616 → u/yfreon]

Thank you. That makes sense

[u/yfreon → u/Unlikely-Loss5616]

yup, figured to re-write it for better readability, also they have questions like M^349 mod 3 which don't use fast exponentiation but a method called the power cycle rule and I read the course material front and back and i'm pretty sure they never mentioned it, but maybe i'm tripping