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?

  • $\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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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