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?
3
$\begingroup$
$\endgroup$
-
$\begingroup$ Your image is invisible $\endgroup$ – kodlu Sep 7 '18 at 18:58
-
$\begingroup$ @kodlu - weird. I can see it in incognito mode where I'm not logged in and where I am logged in. I copied the image from crypto.stackexchange.com/q/20990/4520 if that helps idk $\endgroup$ – neubert Sep 7 '18 at 19:11
2
$\begingroup$
$\endgroup$
$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\}$.
