Hi Guys,
I was wondering if anyone can help me with a proof for the following:
( (S*R)^2 )(mod n)= [( (S^2)(mod n) )(R^2)](mod n)
where:
n = pq, p and q are prime numbers, p and q can be ignored
S < n
R some random integer
thanks
Hi Guys,
I was wondering if anyone can help me with a proof for the following:
( (S*R)^2 )(mod n)= [( (S^2)(mod n) )(R^2)](mod n)
where:
n = pq, p and q are prime numbers, p and q can be ignored
S < n
R some random integer
thanks
in general, for ANY integers r,s:
if we write [k] for k (mod n), [(sr)^2)] = [sr][sr] = [s][r][s][r] = [s]^2[r]^2 = [s^2][r^2].
this is because if a = r mod n, and b = s mod n,
then a = r + kn, b = s + tn, so ab = (r + kn)(s + tn) = rs + (ks + rt + ktn)n, that is:
ab = rs (mod n). this is true whether or not any of the integers involved are between 0 and n or not.