Non-adjacent Form - Obtaining NAF

Obtaining NAF

There are several algorithms for obtaining the NAF representation of a value given in binary. One such is the following method using repeated division; it works by choosing non-zero coefficients such that the resulting quotient is divisible by 2 and hence the next coefficient a zero.

Input: E = (e_{m − 1} e_{m − 2} ··· e₁ e₀)₂

Output: E = (z_m z_{m − 1} ··· z₁ z₀)_NAF

i ← 0

while E > 0 do

if E is odd then

z_i ← 2 − (E mod 4)

else

z_i ← 0

E ← (E − z_i)/2

i ← i + 1

return z