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

========= WAS CANCELLED BY =======:
Path: ...news-out.cwix.com!newsfeed.cwix.com!newscon02.news.prodigy.com!newscon06.news.prodigy.com!prodigy.net!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 16:10:12 -0500
From: tomstdenis@gmail.com
Control: cancel <5$%$$-%%-__%__-_%_$@news.noc.cabal.int>
Subject: Cancel "REPOST: Re: observation on NAF"
Newsgroups: sci.crypt
Date: Tue, 25 Oct 2005 17:32:30 GMT
Message-ID: <4--$-$$$-_$$-$$$_-%@news.noc.cabal.int>
X-Newsreader: MR/2 Internet Cruiser Edition for OS/2 v1.68 b68
Lines: 2
NNTP-Posting-Host: 64.121.22.24
X-Trace: sv3-1cYGEzjd5t01OMHOSOz4INaj6EktZq8Sde3FS1PE+1iM+9F/YYYGJed5hllSETz5MfiJ8GcFMqOwyth!0MHd2r6NrPqYlIcPIiOYalkHB9NwqcEiCba1sD7ThV4Guh4CSNR444LzZHYYGgRQ0xfl0iwoIg==
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. ... I used the trick of generating the digits right-to-left using the ...
    (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
    ... 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)
  • 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)