blob: fe4f24cd64fee4ac384563b002d50d33346c5faa (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
from public import public
from typing import List
@public
def wnaf(k: int, w: int) -> List[int]:
"""
Compute width `w` NAF (Non-Adjacent Form) of the scalar `k`.
:param k: The scalar.
:param w: The width.
:return: The NAF.
"""
half_width = 2 ** (w - 1)
full_width = half_width * 2
def mods(val: int) -> int:
val_mod = val % full_width
if val_mod > half_width:
val_mod -= full_width
return val_mod
result: List[int] = []
while k >= 1:
if k & 1:
k_val = mods(k)
result.insert(0, k_val)
k -= k_val
else:
result.insert(0, 0)
k >>= 1
return result
@public
def naf(k: int) -> List[int]:
"""
Compute the NAF (Non-Adjacent Form) of the scalar `k`.
:param k: The scalar.
:return: The NAF.
"""
return wnaf(k, 2)
|
