Modular Exponentiation

Question

Give an estimate of the maximum number of arithmetic operations required in a fast exponentiation when the exponent has 100 decimal digits.

talked to prof about this review question, didn't really understand the reply, it was along the lines of, 2¹⁰⁰ = 1000 digits = 10^{3 x 10} = 330 binary digits x 2 = 660 operations , just hoping someone could explain the steps to get to 660 operations

Answer 1

The reasoning is probably that a number with $100$ decimal digits will have about $330$ bits -- and using exponentiation by squaring, you will need either one or two modular multiplications per bit position in the exponent, for a worst-case of about $660$ modular multiplications.

This does not count how much work it is to do one modular multiplication (which generally involves one bignum multiplication and a division with remainder, unless you use something like Montgomery reduction), nor does it take into account that squarings of large numbers can be done somewhat cheaper than general multiplications.

Answer 2

The algorithm consists in squaring at most $n$ times if the exponent is $2^n$, and multiplying when the quotient of the exponent by $2$ in the procedure is odd. So there are at most $n$ squarings and $n$ multiplication – in all at most $2n$ arithmetic operations.

That said an exponent with $100$ decimal digits is an exponent $\; <10^{100}=\bigl(10^3\bigr)^{\tfrac{100}3}<\bigl(2^{10}\bigr)^{33.4}$ $=2^{334}$. So the algorithm will require at most $668$ arithmetic operations.

Description of the algorithm in pseudo-code:

Input: exponent N, number $a$

Output: $a^N$.

Variables: $x, n, P$.

Initialisation: $x\leftarrow a,\;n \leftarrow N, \;P\leftarrow 1$.

WHILE $n>0$ DO

$\qquad$ IF $n$ ODD DO $\;P\leftarrow x*P\;$ ENDIF;

$\qquad\; n\leftarrow \lfloor n/2\rfloor$; $ x\leftarrow x^2$;

ENDWHILE

OUTPUT $P$