Join Log in
Score:2
Myria avatar Crypto

Is there an algorithm to compute the wNAF for an exponent faster than quadratic?

in flag
Myria

For doing exponentiation in a group for which inversion is trivially easy, such as elliptic curve groups, is there an algorithm for computing the $w$NAF ("$w$-ary non-adjacent form") array faster than $O(n^2)$? The standard algorithm is listed on Wikipedia as (translated to Python):

def wnaf(d):
    result = []
    for i in range(256):
        if d & 1:
            di = mods(d)
            d -= di
            result += [di]
        else:
            result += [0]
        d >>= 1
    return result[::-1]

The quadratic part here is that di can be negative, turning the subtraction into addition. This can carry all the way to the top of the number, so processing the entire value of d is potentially necessary for each iteration, making the algorithm quadratic in the number of bits.

Is there a better way to do this?

50
0 + 0
Score:2
Daniel S avatar Crypto
ru flag
Daniel S

Fun question! The answer is yes. The trick is to modify the loop according to the sign of the last window. If the last window was positive, we skip over 0s and stop at the next 1; if the last window was negative, we skip over 1s and stop at the next 0 and flip it. I think that there is also a final step for both this and the algorithm quoted in the question where if the final window is negative we need to prepend a 1. Here's my best stab at some python for windows of width $w$.

def wnaf2(d):
    result = []
    sign = 0
    while d !=0:
        if (d & 1)^sign:
            di = mods(d^sign)
            sign = (d>>(w-1)&1)   # There's a case for rolling this into the mods function
            d = d>>w              # Just wipe out the last window without carries
            result += [di]
            result += (w-1)*[0]
        else:
            result += [0]
            d >>= 1
    if sign:
        result += [1]
    return result[::-1]

This is linear provided that we are counting shifts and masking as $O(1)$ operations.

0 + 0
Myria avatar
in flag
Myria
The shifts and masking are $O(1)$ in a real implementation (i.e. not Python) because rather than actually shifting the whole `d` we can just index the bytes and bits. This solves the problem I was having. Thanks! <3
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.