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
- $x^{11}$ (from precomputation, no multiplication)
- Square $x^{11}$ for 4 times we have $x^{176}$. Multiply it by $x$, we have $x^{177}$
- 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}$
- 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}$
- 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.