wNAF

wnaf.py

def mods(ki, w):
    if ki >= (1 << (w-1)):
        return ki - (1 << w)
    else:
        return ki

def wnaf(k, w):
    assert(w >= 2)
    mask = (1 << w) - 1
    naf = []

    while k > 0:
        ki = 0
        if k % 2 == 1:
            ki = mods(k & mask, w)
            k -= ki
            assert((k & mask) == 0)
        k = k // 2
        naf.append(ki)

    naf.reverse()
    return naf

def check_naf(naf, w, ek):
    k = 0
    for n in naf:
        k <<= 1
        k += n
    assert(k == ek)

l = 7237005577332262213973186563042994240857116359379907606001950938285454250989
#l = 1122334455
#l = 11957708941720303968251

for w in [2, 3]:
    naf = wnaf(l, w)
    print("wNAF(%d) = %s" % (w, ", ".join(["%d" % x for x in naf])))
    check_naf(naf, w, l)
    
  def stats(naf):
    zeros = 0
    nonzero = 0

    for n in naf:
        if n == 0:
            zeros += 1
        else:
            nonzero += 1

    return (zeros, nonzero)

print(stats(wnaf(l, 2)))
print(stats(wnaf(l, 3)))