# Textbook Definition of Non-Adjacent Form (NAF)

## What is NAF
The non-adjacent form (NAF) of a positive number is a unique signed-digit representation, in which _non-zero values are non-adjacent_ [1].

For example [2], among the representations of $11$ below, the third representation in red is the only NAF form.
\begin{matrix}
(0 & 1 & 0 & 1 & 1) & \equiv & (8+2+1)=11 \\
(0 & 1 & 1 & 0 & -1) & \equiv & (8+4-1)=11 \\
(\color{red}{1} & \color{red}{0} & \color{red}{-1} & \color{red}{0} & \color{red}{-1}) & \equiv & (16-4-1)=11 \\
(1 & -1 & 1 & 0 & -1) & \equiv & (16-8+4-1)=11 \\
(1 & -1 & 0 & 1 & 1) & \equiv & (16-8+2+1)=11 \\
\end{matrix}

In the above discussion, we considered the integers
$\{−1,0,1\}$ to be used in the NAF. This is referred to as a 2-bit windowed NAF (wNAF). It is possible to increase the window size to reduce the number of non-zero entries.

The main benefit of NAF is that the Hamming weight (number of non-zero digits) of the value will be minimal. For regular binary representations of values, half of all bits will be non-zero, on average, but with NAF this drops to only one-third of all digits [1].

The cost of a textbook double-and-add method to calculate $kP$ is proportional to the Hamming weight of the scalar $k$. Therefore, NAF is helpful to reduce the cost of single scalar multiplication $kP$.

## Compute NAF
An efficient algorithm to calcuate NAF(k) was given in algorithm 3.30 [3].

input: positive integer k
output: NAF(k) = {k_i}

i = 0
while k >= 1 do
    if k is odd: k_i = 2 - (k mod 4), k = k - k_i
    else: k_i = 0
    k = k / 2
    i = i + 1
return k_i-1, k_i-2 ..., k_0

## References
[1] https://en.wikipedia.org/wiki/Non-adjacent_form

[2] https://hackmd.io/@aztec-network/rJ3VZcyZ9

[3] Darrel Hankerson, Alfred J. Menezes, Scott Vanstone, Section 3.3, [_Guide to Elliptic Curve Cryptography_](https://link.springer.com/book/10.1007/b97644), 2004

###### tags: `public`