REPOST: Re: observation on NAF

tomstdenis_at_gmail.com
Date: 10/25/05 

Date: 25 Oct 2005 07:44:23 -0700

James Muir wrote:
> > 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.

I used the trick of generating the digits right-to-left using the
"mods" algorithm [which took me a while to get working arrg...].

I just don't see it. 4NAF is supposed to get me on average 1/5 density
which should be faster than my 4-bit sliding window. Assuming the cost
of making the NAF right-to-left is << a point addition I should at
least BREAK EVEN with the cycle counts.

My hunch is the density isn't as low as they suspect or my naf
generator is REALLY slow [not impossible but I doubt it].

I have noticed a ~.5M cycle drop for P-192 by using the diminished
radix reduction [though I'm stuck, for some reason my projective point
addition is failing but the double and map [back to affine] are working
ok...] which is where I'm focusing my energy [32-bit and 64-bit x 5
curves == lots of time].

To be honest I don't see the benefit in all but the most limited
devices [where you wouldn't put LTC anyways unless you trim it]. For
just a few more hundred bytes of memory you can use the sliding window
which gets you a density of at least on average ~1/4.5 [for the 4 bit
window] and is directly computable.

Tom

========= WAS CANCELLED BY =======:
Path: ...newsfeed.news2me.com!nx01.iad01.newshosting.com!newshosting.com!216.196.98.140.MISMATCH!border1.nntp.dca.giganews.com!nntp.giganews.com!local01.nntp.dca.giganews.com!nntp.rcn.net!news.rcn.net.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 25 Oct 2005 15:02:57 -0500
From: tomstdenis@gmail.com
Control: cancel <1130251463.131854.219700@o13g2000cwo.googlegroups.com>
Subject: Cancel "Re: observation on NAF"
Newsgroups: sci.crypt
Date: Tue, 25 Oct 2005 16:36:06 GMT
Message-ID: <4453105824.533770.578185@o13g2000cwo.googlegroups.com>
X-Mailer: Mozilla 4.5 [en]C-CCK-MCD Boeing Kit (Win98; U)
Lines: 2
NNTP-Posting-Host: 64.121.22.24
X-Trace: sv3-UGkQV83gr7MG42t2g4TgEyppRk/Jk/oqCp1l+h4Drzd9Y4djZyTxp61ccGcvAxoqkkazxX5gbcAeySV!jIznum5sELXZe+hosokfPb3XMzbxhgTdU1TQ70Tc/dTV/Ki6ybzzCwMDPWZg5lxTEx2hrDEGP4zq!smjIdH2UiX91q6dvNw==
X-Complaints-To: abuse@rcn.net
X-DMCA-Complaints-To: abuse@rcn.net
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.32

Relevant Pages

  • REPOST: Re: observation on NAF
    ... > There is a neat trick for constructing the wNAF that you might find ... > binary representation by doing a digitwise subtraction of n from 2n ... > digits as the w-NAF and has the same under of nonzero digits. ... My hunch is the density isn't as low as they suspect or my naf ...
    (sci.crypt)
  • Re: observation on NAF
    ... > There is a neat trick for constructing the wNAF that you might find ... > binary representation by doing a digitwise subtraction of n from 2n ... > digits as the w-NAF and has the same under of nonzero digits. ... I used the trick of generating the digits right-to-left using the ...
    (sci.crypt)
  • REPOST: Re: observation on NAF
    ... There is a neat trick for constructing the wNAF that you might find ... It is based on a special radix 2 representation of an ... digits as the w-NAF and has the same under of nonzero digits. ... Subject: Cancel "Re: observation on NAF" ...
    (sci.crypt)
  • Re: observation on NAF
    ... > compute NAF directly like you can for the unsigned window [e.g. just ... There is a neat trick for constructing the wNAF that you might find ... It is based on a special radix 2 representation of an ... digits as the w-NAF and has the same under of nonzero digits. ...
    (sci.crypt)
  • Re: Gentler Decimal Floating-Point
    ... effectively change the radix of a decimal floating point ... under the heading "Logarithms all the time", ... logarithmic representation of numbers to be made workable for all the ... The middle digits are shifted only when the exponent, ...
    (comp.arch.arithmetic)