I am trying to understand the modular exponentiation algorithm. Why is it that:
$x^2 \mod5 = (x\mod5)(x\mod5) \mod 5$
What is the basic reasoning behind this?
I am trying to understand the modular exponentiation algorithm. Why is it that:
$x^2 \mod5 = (x\mod5)(x\mod5) \mod 5$
What is the basic reasoning behind this?
Write $x = m + 5n$ with $0 \leq m \leq 4$. No matter what you multiply $5n$ by, the result will be a multiple of $5$ and subsequently dropped by the "mod $5$" at the end. So, you might as well have dropped the $5n$ to begin with. That is, you could just take $x$ mod $5$ before carrying out the multiplication.
I am not sure about the doubt in ur mind but i hope i am answering ur question! The reason for the last mod5 in the rhs is to ensure that the lhs and the rhs are compatible.As the lhs is a residue it is by defn a value between 0 & 5.However if u drop the final mod5 the rhs may not be a residue(note that it is a product of two residues,so not necessarily a residue by itself!). eg x=4 implies lhs =1 without the final mod5 the rhs value=16 !