choices for k in binary finite field modular reduction algorithm

Question

In the Guide to Elliptic Curve Cryptography there's this algorithm:

My question is... what is $k$? Is it just some random value we pick? If so are some numbers better than others?

Answer 1

$W$ is the size of the words we are operating on, and hence $u_k(z)$ is a precomputed polynomial for each bit of a word (note $0 \le k \le W-1$), defined as $z^kr(z)$. So if we have 32 bit words we have 32 precomputed polynomials, indexed by $k$.

Then, in the actual algorithm, at each step we compute $k$ as $(i - m) - Wj$, and use that value $k$ to select one of our precomputed polynomials, which we add to $C\{j\}$. So $k$ is not randomly selected, it is deterministically computed at each step of the algorithm and then used to select a precomputed polynomial.

As an example, if we are at a step where $i = 128, j = 2, m = 64, W = 32$ we would compute $k = (128 - 64) - 32 * 2 = 0$. So we would add $u_0(z) = z^0r(z) = r(z)$ to $C\{j\}$.