How many multiplications are needed when one applies the algorithm to computing $132^{1023} \mod 2047$?

Question

Suppose the integer $a$ has binary representation $b_kb_{k-1}\cdots b_1b_0$ where $b_i$ are either $0$ or $1$. The power $x^a \mod n$ can be computed using the fast exponential algorithm. The calculation can be organized via the following table:

\begin{table}[h]
    \begin{tabular}{|l|l|l|l|l|}
    \hline
    j        & $b_j$    & $X_j=x^{2^j} \mod n$   & $A_j$                     \\ \hline
    0        & $b_0$    & $X_0=x \mod n$         & $A_0=X_0^{b_0}$           \\ 
    1        & $b_1$    & $X_1=X_0^2 \mod n$     & $A_1=X_1^{b_1}A_0 \mod n$ \\ 
    2        & $b_2$    & $X_2=X_1^2 \mod n$     & $A_2=X_2^{b_2}A_1 \mod n$ \\ 
    $\vdots$ & $\vdots$ & $\vdots$               & $\vdots$                  \\ 
    k        & $b_k$    & $X_k=X_{k-1}^2 \mod n$ & $A_k=X_k^{b_k}A_{j-1} \mod n$ \\
    \end{tabular}
    \end{table}

Each entry of the third column is obtained from the entry above by squaring and then reducting modulo $n$. Note also $A_j=A_{j-1}$ wherever $b_i=0$.

Question: How many multiplications are needed when one applies the algorithm to computing $132^{1023} \mod 2047$?

How would I do these problem?

Answer 1

Hint: Each time you square $132$ you double the exponent. How many doublings are needed to get the largest power of $2$ less than $1023$? Having computed all these $132^{2^n}$s, you need to multiply a number of them together. How many? How many $1$'s are in the binary representation of $1023$ Why is that useful?