2
$\begingroup$

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

Modulus Reduction

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

$\endgroup$
2
  • $\begingroup$ Your image is invisible $\endgroup$
    – kodlu
    Commented Sep 7, 2018 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
    Commented Sep 7, 2018 at 19:11

1 Answer 1

2
$\begingroup$

$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\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.