• Article
  • | |
  • Metrics
  • |
  • Reference [8]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    J.A.Solinas suggested an optimal signed binary representation for pairs of integers, which is called a Joint Sparse Form (JSF). JSF is at most one bit longer than the binary expansion of the larger of the two integers, and the average joint Hamming density among Joint Sparse Form representations is 1/2. This paper extends the Joint Sparse Form by using a window method, namely a new representations, for pairs of integers, which is called Width-3 Joint Sparse Form (JSF3). The representation is at most one bit longer than the binary expansion of the larger of the two integers, and the average joint Hamming density is 19/52. So, computing the form of uP+vQ by using JSF3 is almost 9% faster than that by using JSF.

    Reference
    [1]Cohen H.A Course in Computational Algebraic Number Theory.Berlin:Springer-Verlag,1993.
    [2]Gordon DM.A survey of fast exponentiation methods.Journal of Algorithms,1998,27(1):129-146.
    [3]Brown M,Hankerson D,Lopez J,Menezes A.Software implementation of NIST elliptic curves over prime fields.In:Naccache D,ed.Topics in Cryptology-CT-RSA 2001.LNCS 2020,Berlin:Springer-Verlag Heidelberg,2001.250-265.
    [4]Avanzi R.On multi-exponentiation in cryptography.2003.http://citeseer.ist.psu.edu/avanzi02multiexponentiation.html
    [5]Bernstein DJ.Pippenger'2 exponentiation algorithm.2002.http://cr.rp.to/papers.html
    [6]Ciet M,Lange T,Sica F,Quisquater JJ.Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms.In:Biham E,ed.Advances in Cryptology-Eurocrypt 2003,LNCS 2656.Berlin,Heidelberg:Springer-Verlag,2003.388-400.
    [7]Morain F,Olivos J.Speeding up the computations on an elliptic curve using addition-subtraction chains.Informatique Theorique et Applications/Theoritical Informatics and Applications,1990,24(6):531-543.
    [8]Chung KL.Elementary Probability Theory with Stochastic Processes.3rd ed.Berlin:Springer-Verlag,1978.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

张亚娟,祝跃飞,况百杰.整数对的低重量表示JSF3.软件学报,2006,17(9):2004-2012

Copy
Share
Article Metrics
  • Abstract:4815
  • PDF: 6161
  • HTML: 0
  • Cited by: 0
History
  • Received:November 03,2003
  • Revised:July 28,2005
You are the first2032798Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063