Two Lower Bounds for Shortest Double-Base Number System

• CHALERMSOOK Parinya

  Department of Algorithms and Complexity, Max-Planck-Institut für Informatik

• IMAI Hiroshi

  Graduate School of Information Science and Technology, The University of Tokyo

• SUPPAKITPAISARN Vorapong

  Global Research Center for Big Data Mathematics, National Institute of Informatics JST, ERATO Kawarabayashi Large Graph Project

Abstract

In this letter, we derive two lower bounds for the number of terms in a double-base number system (DBNS), when the digit set is {1}. For a positive integer n, we show that the number of terms obtained from the greedy algorithm proposed by Dimitrov, Imbert, and Mishra [1] is $\Theta\left(\frac{\log n}{\log \log n}\right)$. Also, we show that the number of terms in the shortest double-base chain is Θ(log n).

Journal

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E98.A (6), 1310-1312, 2015

  The Institute of Electronics, Information and Communication Engineers

Keywords

• analysis of algorithms
• number representation
• elliptic curve cryptography
• double-base number system
• double-base chain

Details

• CRID: 1390001206310805376
• NII Article ID: 130005071813
• NII Article ID: 120006904165
• DOI: 10.1587/transfun.e98.a.1310
• ISSN: 17451337
• ISSN: 09168508
• HANDLE: 2261/00074093
• Web Site: https://repository.dl.itc.u-tokyo.ac.jp/records/48968
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E98.A/6/E98.A_1310/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed