Integer Exponentiation Modulo p

The problem of Exponentiation Modulo p is defined as follows: Given two positive integers a and b$,$ and

a prime number p$,$ compute the value of a$^$b modulo p $($i$.$e$.,$ the remainder when dividing a raised to the

power of b by p$).$ The Montgomery exponentiation algorithm is a randomized algorithm for efficient

exponentiation modulo a prime number.

$($a$)$ Briefly describe the underlying idea behind the Montgomery exponentiation algorithm.

$($b$)$ Specify and justify the type of the Montgomery exponentiation algorithm $($Las Vegas or Mont Carlo$)$

$($c$)$ Analyze the expected running time complexity of the algorithm.

$($d$)$ Discuss the potential trade$-$offs between using a randomized algorithm compared to a deterministic

approach.