Re: observation on NAF

From: James Muir (noone_at_127.0.0.1)
Date: 10/25/05


Date: Tue, 25 Oct 2005 10:36:28 -0400


> I've tried 3NAF and 5NAF [it's easily switchable] and their doesn't
> seem to be an improvement. It's also a bit annoying that you can't
> compute NAF directly like you can for the unsigned window [e.g. just
> take the bits verbatim].

There is a neat trick for constructing the wNAF that you might find
useful. It is based on a special {0,1,-1} radix 2 representation of an
integer.

Suppose we want to build the 3-NAF of an integer n which has the binary
representation 111011100010101. First, we construct the special signed
binary representation by doing a digitwise subtraction of n from 2n

2n 1 1 1 0 1 1 1 0 0 0 1 0 1 0 1 0
  n 1 1 1 0 1 1 1 0 0 0 1 0 1 0 1

n 1 0 0 -1 1 0 0 -1 0 0 1 -1 1 -1 1 -1

Now we slide a 3-digit window from right-to-left across the representation:
        
n 1 0 0 0 1 0 0 -1 0 0 0 0 3 0 0 -3

This gives us the 3-NAF.

However, you can also slide the window *left-to-right* over the special
signed binary rep and you will get a representation which uses the same
digits as the w-NAF and has the same under of nonzero digits. What's
nice about going left-to-right is that you don't need to store the
digits of the new representation before you compute a scalar
multiplication -- you can just process them on the fly.

I would be interested to know if you observe any speed-up by
constructing your representation left-to-right.

-James