Non-adjacent form (NAF)

NAF is a signed-digit representation. It’s a unique integer representation. In NAF representation, two non-zero values cannot be adjacent. In cryptography using, NAF representation reduces number of multiplications needed for performing exponentiation.

Example:
7 can have several binary representations:

(0 1 1 1) = 4 + 2 + 1 = 7

(1 0 −1 1) = 8 − 2 + 1 = 7

(1 −1 1 1) = 8 − 4 + 2 + 1 = 7

(1 0 0 −1) = 8 − 1 = 7

But only the last representation is NAF.

The algorithm is:

Input: E = (em − 1 em − 2 ··· e1 e0)10
Output: E = (zm zm − 1 ··· z1 z0)NAF

i ← 0
while E > 0 do
if E is odd then
zi ← 2 − (E mod 4)
else
zi ← 0
E ← (E − zi)/2
i ← i + 1
return z

The coding implementation will be done as soon as the phd student finish writing progress report, presentation slides and simulating small curves for progress seminar.

Advertisements