cs150

Open full view…

hey professor, question ab

leosorkin
Tue, 12 Apr 2016 04:15:55 GMT

out hw9 if you will: is it true that a^k ≡ b^k (mod n)? Also, is Fermat's little theorem the most optimal way to solve problem 2 (out of all that we've learned)?

alexey
Sat, 16 Apr 2016 00:52:49 GMT

_a^k ≡ b^k (mod n)_ is not always true (or I'd say, very frequently it's not true at all). For example: _2^2 =/= 3^2 (mod 10)_... (because _4 =/= 9_) Regarding problem 2: Your primary concern should be the correctness of your solution, not so much its optimality. I actually don't care if your solution is optimal or not... However, that said, Fermat's little theorem is very convenient for doing exponentiation. Still, before using it, you have to make sure that all its requirements are met (otherwise it would be a mistake to apply it).