Answer:
Step-by-step explanation:
To compute f(x) = INM-o a, x' using a simple routine to perform exponentiation, we need to perform N modular multiplications and N modular squarings, where N is the number of bits in the binary representation of the exponent M.
The time required to perform a single modular multiplication is proportional to the square of the number of bits in the operands, and the time required to perform a single modular squaring is proportional to the number of bits in the operand. Therefore, the total time required to compute f(x) using a simple routine to perform exponentiation is proportional to:
N*(k1n^2 + k2n)
where k1 and k2 are constants that depend on the specific implementation, and n is the number of bits in the operands.
Since we do not know the specific values of k1 and k2, we cannot calculate the exact amount of time required to compute f(x). However, we can say that the time required will grow exponentially with the number of bits in the exponent M.
In general, modern computers use more efficient algorithms for exponentiation, such as square-and-multiply or Montgomery exponentiation, which require fewer modular multiplications and squarings than a simple routine. As a result, these algorithms are much faster than a simple routine for large values of the exponent M.