是否有一種算法可以比二次方更快地計算指數的 wNAF？

對於在一個反演非常容易的組中進行取冪，例如橢圓曲線組，是否有一種算法可以計算 $ w $ NAF (" $ w $ -ary 非相鄰形式") 數組快於 $ O(n^2) $ ? 標準算法在Wikipedia 上列為（翻譯成 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]

這裡的二次部分di可以是負數，將減法變成加法。這可以一直帶到數字的頂部，因此d每次迭代都可能需要處理 的整個值，從而使算法在位數上呈二次方。

有一個更好的方法嗎？

有趣的問題！答案是肯定的。訣竅是根據最後一個視窗的符號修改循環。如果最後一個視窗是正數，我們跳過 0 並在下一個 1 處停止；如果最後一個視窗是負數，我們跳過 1s 並在下一個 0 處停止並翻轉它。我認為這和問題中引用的算法還有最後一步，如果最終視窗為負，我們需要在前面加上 1。這是我對寬度視窗的一些 python 的最佳嘗試 $ 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]

這是線性的，前提是我們將班次和掩蔽計算為 $ O(1) $ 操作。

引用自：https://crypto.stackexchange.com/questions/96482