Average number of multiplications in left-to-right k-ary exponentiation

Question

On page 617 in chapter 14 of The Handbook of Applied Cryptography, the average number of multiplications in left-to-right k-ary exponentiation is $ l\times (2^k-1)/2^k$, where $l=\lfloor t/k\rfloor $, i.e. the number of k words in the $t+1$ bits exponent after excluding the leading 1. My question is, do the residual $t\;mod\; k$ bits require one extra multiplication when it is even, because we only precompute the odd number < $2^k$ ? If this argument is true, how should I calculate the correct average number of multiplications?

Thank @galvatron, especially for CPython implementation. May I use an example to make my question clear.Let's say I want to calculate $x^{364086}$ with $k=4$. Because $364086=1011|0001|1100|0110|110_{2}$,$t+1=19$, $t=18$ and $l=\lfloor18/4\rfloor$=4. We will precompute $x^3$, $x^5$, $x^7$, $x^9$, $x^{11}$,$x^{13}$,$x^{15}$. Then calculate steps are

1. $x^{11}$ (from precomputation, no multiplication)
2. Square $x^{11}$ for 4 times we have $x^{176}$. Multiply it by $x$, we have $x^{177}$
3. Square $x^{177}$ for 2 times, we have $x^{708}$. Multiply it by $x^3$, we have $x^{711}$. Sqaure $x^{711}$ for 2 times, we have $x^{2844}$
4. Square $x^{2844}$ for 3 times,we have $x^{22752}$.Multiply it by $x^3$, we have $x^{22755}$. Square $x^{22627}$ for 1 times, we have $x^{45510}$
5. Sqaure $x^{45510}$ for 2 times, we have $x^{182040}$. Multiply it by $x^3$, we have $x^{182043}$.Square it for one time, we have $x^{364086}$ (This is the residual bits which require one multiplication, but the chance this residual bits require multiplication is not precisely $(2^{4}-1)/2^{4}$, instead it is $(2^{3}-1)/2^{3}$)

I make a serious error that first k-bits word need one time of multiplication, and I apologize for it. However I still had some questions about this algorithm in the book. The handbook also says the worst scenario require $l-1$ multiplication, but in this case we have to perform $4>l-1$ times of multiplication.

Answer 1

In Algorithm 14.82, you divide the exponent into $2^k$ windows. In the pre-compute stage, you encode those "bit-windows" into products of $x$. All of those bit-windows will be involved in multiplications except the $000...00_2$ window, which will be encoded as 1, hence no multiplication (I'm assuming $x\cdot 1$ is trivial).

Here's the trick: on average you're equally likely to be using the other $2^k - 1$ bit-windows. Another way of saying this is that you have a probability $\frac{2^k-1}{2^k}$ to pick a bit-window that isn't $000...000_2$. How many bit-windows did we split the exponent into? Precisely $\lfloor{t/k}\rfloor$, or $l$.

So the average number of multiplications (that aren't pre-computations or squarings) is $l\cdot \frac{2^k-1}{2^k}$. You don't have to worry about the evenness of the residual bits at all.

Advice

In practice, 14.85 (the sliding window method) is more efficient in practice, even if it's hard to count the number of steps it takes (as noted on page 617). If you're trying to implement something, check that one out. As a real-world example, CPython, the usual C implementation of Python, uses 14.82 for large modular exponentiation. They choose $k=5$ as that seems to work well in practice.

Example

I copied an example from here to count the multiplications.

Looking at Algorithm 14.82 on page 615, let's say I wanted to calculate $x^{250}$ and let $k=2$, or $b=2^2=4$. Write $250 = (11111010)_2$. With a window of $2$, you have $11|11|10|10$.

First, let's make the pre-computation table: even though we only need $11_2$ and $10_2$, let's follow 14.82 anyway:

$00_2\rightarrow 1$

$01_2\rightarrow x$

$10_2\rightarrow x\cdot x = x^2$

$11_2\rightarrow x^2 \cdot x = x^3$

We have four "bit-windows", only $3 = 4-1$ of which will be involved in multiplying something that isn't $1$.

Now, in the algorithm, step 3.1 is the "squaring" step, except we're multiplying by $x^{2^2}$ each time. After each "squaring" step, we have a multiplication step using the table above. So taking the bits two at a time we have:

$11_2: x^3, x^3$

$11_2: (x^3)^4=x^{12}, x^{12}\cdot x^3 = x^{15}$

$10_2: (x^{15})^4=x^{60}, x^{60}\cdot x^2 = x^{62}$

$10_2: (x^{62})^4=x^{248}, x^{248}\cdot x^2 = x^{250}$

The middle column is the squaring step (3.1), and the right column is the multiplication step (3.2).

So that gives us $2$ multiplications in the precompute stage, $6$ squarings (or $3$ "raising to the fourths"), and $3$ multiplications.

In this example, $t=8$, so $l = 4, 2^k = 4$, so the formula gives $4 \cdot 3/4 = 3$.

If you do the same thing with $k=3, b = 8$, you get $6$ precompute multiplications, $6$ squarings, and $2$ multiplications. In that case, our formula gives $l = \lfloor{8/3}\rfloor = 2$, and $2^k = 8$, so we calculate $14/8 \approx 2$ multiplications. Close enough?