The Non-Adjacent Form (NAF) of an integer is a signed-binary representation using digits from {-1, 0, 1} in which no two consecutive digits are both nonzero. Every integer has a unique NAF, and among all signed-binary representations of a value it has the minimum possible number of nonzero digits (on average about n/3 nonzeros for an n-bit number, vs. n/2 for ordinary binary). This makes it the standard tool for speeding up multiplication and modular exponentiation, since each nonzero digit costs one add/subtract. Implement `toNAF(n)` that converts an integer `n` (which may be negative) to its NAF, returning the digits least-significant-first as a list of values from {-1, 0, 1}. Key idea: repeatedly look at the value. If it is even, emit a 0 and halve it. If it is odd, choose the digit z in {-1, 1} so that n - z is divisible by 4 (this forces the NEXT digit to be 0, guaranteeing the non-adjacency property). The choice is z = 2 - (n mod 4): that yields +1 when n ≡ 1 (mod 4) and -1 when n ≡ 3 (mod 4). Emit z, subtract it from n, then halve. Stop when n reaches 0. By convention NAF(0) is [0]. Proof sketch of correctness: when n is odd, n mod 4 is 1 or 3. If n ≡ 1 (mod 4) we pick z=1, making n-1 ≡ 0 (mod 4), so (n-1)/2 is even and the next emitted digit is 0. If n ≡ 3 (mod 4) we pick z=-1, making n+1 ≡ 0 (mod 4), again forcing the next digit to 0. Thus no two adjacent nonzero digits ever appear, and the running value provably converges to 0 (its magnitude strictly decreases each two steps), so the loop terminates and reconstructs n exactly. Minimality: NAF is the unique signed-binary representation with no two adjacent nonzeros, and a classic result (Reitwiesner) shows this canonical form minimizes the Hamming weight (count of nonzero digits) over all signed-binary representations of the same integer — which is exactly why it minimizes additions in scalar multiplication.

Given a Non-Adjacent Form (NAF) sequence — a list of signed-binary digits from {-1, 0, 1}, least-significant-first — reconstruct the integer it represents. The value of a digit list d is simply the weighted sum sum(d[i] * 2^i). The digits being from {-1, 0, 1} (rather than {0, 1}) is exactly what lets the representation be signed; the reconstruction does not actually depend on the non-adjacency property, so this same routine inverts any signed-binary digit list. Implement `fromNAF(digits)` returning the integer. The numerically stable way to evaluate it is Horner's method from the most-significant digit down: start with value 0 and repeatedly do value = value * 2 + digit, walking the list from its last element to its first. An empty list represents 0. This is the inverse of `toNAF`, so `fromNAF(toNAF(n)) == n` for every integer n. As the extension in the prompt notes, this pairing is what powers fast multiplication n*k: precompute toNAF(k), then accumulate shifted copies of n with a +n for each +1 digit and a -n for each -1 digit, performing about |k|'s NAF-weight additions/subtractions instead of one per binary one.