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
SomeExplicitFormulaeofNAFand
itsLeft-to-RightAnalogue
Dong-GukHan1,TetsuyaIzu2,andTsuyoshiTakagi1
FUTUREUNIVERSITY-HAKODATE,
116-2Kamedanakano-cho,Hakodate,Hokkaido,041-8655,Japan
{christa,takagi}@fun.ac.jp2FUJITSULABORATORIESLtd.,
4-1-1,Kamikodanaka,Nakahara-ku,Kawasaki,211-8588,Japan
izu@labs.fujitsu.com1
Abstract.Non-AdjacentForm(NAF)isacanonicalformofsignedbi-naryrepresentationofintegers.WepresentsomeexplicitformulaeofNAFanditsleft-to-rightanalogue(FAN)forrandomlychosenn-bitin-tegers.Interestingly,weprovethatthezero-runlengthappearedinFANisasymptotically16/7,whichislongerthanthatofthestandardNAF.Wealsoapplytheproposedformulaetothespeedestimationofellipticcurvecryptosystems.
Keywords:signedbinaryrepresentation,non-adjacentform,Hammingweight,zero-runlength.
1Introduction
Insomeexponentiation-basedpublic-keycryptosystemsincludingRSAandEl-lipticCurveCryptosystems(ECC),abinaryrepresentationofagiveninteger(whichmaybeasecretinmostcases)iscommonlyusedasastandardtech-nique.Whileanon-signedrepresentationofanintegerisunique,wehavesomewaysforrepresentingtheintegerinsignedform.Forexample,aninteger13canberepresentedinsignedformsuchas10¯101,100¯1¯1,or10¯11¯1,where¯1denotes 1.SuchsignedbinaryrepresentationsareespeciallyusefulinECC,sinceinver-sionsofarbitrarypointscanbeobtainedwithalmostfreeoperationsoverellipticcurves.Somepropertiesofsuchsignedbinaryrepresentationsarerelatedtothecostofanexponentiation.Especially,thenumberofnonzerobits(theHammingweight)isimportantsincethisvaluerulesthenumberofmultiplicationsintheexponentiation.Thusanalyzingsignedrepresentationsimpliesacostevaluateofexponentiations.
Thenon-adjacentform(NAF)isawell-knownsignedbinaryrepresentation n 1[Rei60].ANAFofapositiveintegeraisanexpressiona=i=0νi2iwhereνi∈{ 1,0,1},νn 1=0andnotwosuccessivedigitsarenonzero,namelyνi·νi+1=0fori=0,1,...,n 2[Rei60].EachintegerahasauniqueNAFrepresentationdenotedbyNaf(a).Moreover,Naf(a)canbee cientlycomputedbyright-to-leftoperations([IEEE],forexample).In[JY00],Joye-Yenproposedaleft-to-
Some Explicit Formulae o... 暂无评价 14页 免费 Evolution of Electronic ... 暂无评价 9页 免费 NAF算法的改进 暂无评价 4页 2.00元 NaF 暂无评价 2页...
Some Explicit Formulae o... 暂无评价 14页 免费 Evolution of Electronic ... 暂无评价 9页 免费 NAF算法的改进 暂无评价 4页 2.00元 NaF 暂无评价 2页...
热门文档