According to wikipedia, in the precomputation step of the w-ary non-adjacent form (wNAF) point multiplication method you do $d \bmod 2$ and, later, $d \gets \frac{d}2$.

The mod operation doesn't make a lot of sense in the context of a prime finite field since division over a finite field doesn't produce a remainder. Rather, it's the numerator multiplied by the modulo inverse of the denominator. But I guess in this context it can probably just be taken to be the same thing as "is d odd".

But what about $d \gets \frac{d}2$? Outside of the context of prime finite fields that would normally be the same thing as right bit shifting by 1 but in the context of a binary field idk that dividing by two is the same thing as right bit shifting by one. It could be "multiply d by the modulo inverse of 2".

The fact that the while loop is doing while (d > 0) do kinda makes me think it's doing bit shifting but idk.

Any ideas?

up vote 2 down vote accepted

The scalar is a scalar, it is not uncommon to view it in $\mathbb{Z}$ instead of in a field defined by the order of the curve/point (note:it does never make sense to view it in a binary field).

So $d\mod2$ becomes the least significant bit of $d$ and $\frac{d}{2}$ becomes the same thing as $floor(\frac{d}{2})$ which is the same thing as a right shift by 1.

The point of wNAF is computing an exponentiation ($g^k$) or a elliptic point multiplication ($kP$). The fact that the order of $g$ or $P$ can be a prime number and thus $k$ can be interpreted as being an element of a prime field is irrelevant. The algorithm would work even if the order was a composite number.

So yes, when wNAF divides by two, it is a integer division by two e.g. right shift.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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