文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Some Explicit Formulae of NAF and its Left-to-Right Analogue
侵权投诉

Some Explicit Formulae of NAF and its Left-to-Right Analogue

Abstract. Non-Adjacent Form (NAF) is a canonical form of signed binary representation of integers. We present some explicit formulae of NAF and its left-to-right analogue (FAN) for randomly chosen n-bit integers. Interestingly, we prove that the zero-run l

rightanalogue“FAN”1.ItisknownthatNAFandFANcanbegeneratedbyapplyingaslidingwindowmethodwithwidth-2totheBoothencoding[Boo51]inright-to-leftandleft-to-right,respectively[HKP+04,OSS+04].NotethattheBoothencodingwasalsointroducedasthereversedbinaryrepresentationbyKnuth[Knu81,Exercise4.1-27].Inthispaper,theBoothencodingandFANofanintegeraaredenotedbyBooth(a)andFan(a),respectively.

Some Explicit Formulae of NAF and its Left-to-Right Analogue

Fig.1.ArelationoftheBoothencoding,NAF,andFAN.

NAFandFANsharesomeproperties.Actually,theyaregeneratedbythesimilarmannerasabove,andtheHammingweightsofNAFandFANforthesameintegerareexactlysame(Fact1).Inthispaper,weproveanexplicitformuladerivedfromtheBoothencoding(Theorem1),whichevaluatestheaveragenumberoftheHammingweightofNAFandFANrepresentationsasa rstcontribution.Ontheotherhand,NAFandFANhavedi erentproperties.Afundamentalobservationsis,whileNAFdoesnothavesuccessivenonzerobitsintherepresentation,FANcanhave.Becauseofthisdi erence,theyhavedi erentsigni cantlengthonaverage.WeestablishformulaeforthisvalueinTheorem2.Moreover,weshowtheaveragedlengthofzerorunsinNAFandFANinTheorem3.InsomeimplementationsofECCexponentiations,iteratedellipticcurvedoubling(wECDBL)isusedfore ciency.Withouranalysis,astricterevaluationoftheaveragedcostofexponentiationsarepossible.Infact,inECCwith160-bitkeys,FANisabout15.97multiplications(inade nition eld)fasterthanNAF.Combinedwithatechniqueusedin[SS01],FANisabout317.47multiplicationsfasterthanNAF.

Anorganizationofthispaperisasfollows:section2de nessomenotationsandtheBoothencoding,NAFandFAN.Insection3,weprovesomelemmasrequiredforourtheorems.Then,weestablishanexplicitevaluationformulafortheHammingweightinsection4.Wealsoshowevaluationformulaefortheaveragedsigni cantlengthandtheaveragedzeroruns(inNAFandFAN)insection5,6,respectively.Finally,insection7,weapplyourformulaetothecostevaluationofECCexponentiations.

2

2.1PreliminariesNotations n 1

i=0Foragivenn-bitintegera=

followingnotations:

1ai2iwithai∈{0,1},an 1=1,weusetheFANcomesfromthereversedorderofNAF.

2

上一页第2页

你可能喜欢

热门文档

相关文档

  • Amalgamating NAF and NAI

    Some Explicit Formulae o... 暂无评价 14页 免费 Evolution of Electronic ... 暂无评价 9页 免费 NAF算法的改进 暂无评价 4页 2.00元 NaF 暂无评价 2页...

  • Amalgamating NAF and NAI

    Some Explicit Formulae o... 暂无评价 14页 免费 Evolution of Electronic ... 暂无评价 9页 免费 NAF算法的改进 暂无评价 4页 2.00元 NaF 暂无评价 2页...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email