6. The following is an algorithm for fast modular exponentiation:
Procedure fast modular exponentiation (?: integer, ? =
(?௞ିଵ?௞ିଶ … ?ଵ?଴)ଶ expressed as the binary representation, ?:
positive integer)
?????? = 1;
for ? = ? − 1 to 0 {
?????? = (?????? ∗ ??????) ??? ?;
if (?௜ == 1)
?????? = (?????? ∗ ?) ??? ?;
}
return ??????; // the result equals ?
௘ mod ?
(a) Please describe how to calculate ?
଼ଷ mod ? (i.e., the exponent ? =
(83)ଵ଴: decimal representation) by the above algorithm and explain it is
correct. (10%)