###### Regular Signed Digit ####
# Based on:
#   "Exponent recoding and regular exponentiation algorithms"
#   by M. Joye and M. Tunstall. Africacrypt 2003.
# Also appears in:
#   "Selecting Elliptic Curves for Cryptography: An Efficiency
#   and Security Analysis", by Bos, Costello, Longa, Naehrig.
def signed(n,w,t):
    k = []
    for i in range(t):
        ki = (n%2**w)-2**(w-1)
        k += [ki]
        n = (n-ki)>>(w-1)
    k += [n]
    return k

# SignedDigit obtains the signed-digit recoding of n and returns a list L of
# digits such that n = sum( L[i]*2^(w-1) ), and each L[i] is an odd number
# in the set {±1, ±3, ..., ±2^(w-1)-1}. The third parameter ensures that the
# output has ceil(l/(w-1)) digits.
# Restrictions:
#  - n > 0.
#  - 1 < w < 32.
#  - l >= bit length of n.
def eval(K,w):
    return sum([ ki*2**(i*(w-1)) for i,ki in enumerate(K) ])


## This script finds scalars k that triggers the requirement of complete
#  addition formula at Step 19.
locat = lambda x: [ i for i,k in enumerate(x) if k]
for w in range(2,20):
    T = [2*i+1 for i in range(0,2**(w-2))]
    LT = [ signed(r-2*ti,w,384/(w-1)) for ti in T ]
    test = [ 2**(w-1)*eval(L[1:],w) == r-ki for L,ki in zip(LT,T) ]
    idx = locat(test)
    if idx != [] :
        print("w: {0}".format(w))
        for id in idx:
            k0 = eval(LT[id],w)
            k1 = r-2*T[id]
            assert(k0==k1)
            assert(k0<r)
            assert(is_odd(r-2*T[id]))
            print("ki: {0}".format(T[id]))
            print("k = 0x{0:x}".format(2*T[id]))
            print("k = r - {0} = 0x{1:x}".format(2*T[id],(k0)))

# EOF