Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

   
 
 

 

Lower bounds on the lengths of double-base representations


Authors: Vassil S. Dimitrov and Everett W. Howe
Journal: Proc. Amer. Math. Soc. 139 (2011), 3423-3430
MSC (2010): Primary 11A67; Secondary 11A63
DOI: https://doi.org/10.1090/S0002-9939-2011-10764-0
Published electronically: February 9, 2011
MathSciNet review: 2813374
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A double-base representation of an integer $ n$ is an expression $ n = n_1 + \cdots + n_r$, where the $ n_i$ are (positive or negative) integers that are divisible by no primes other than $ 2$ or $ 3$; the length of the representation is the number $ r$ of terms. It is known that there is a constant $ a >0$ such that every integer $ n$ has a double-base representation of length at most $ a\log n / \log\log n$. We show that there is a constant $ c>0$ such that there are infinitely many integers $ n$ whose shortest double-base representations have length greater than $ c\log n / (\log\log n \log\log\log n)$.

Our methods allow us to find the smallest positive integers with no double-base representations of several lengths. In particular, we show that $ 103$ is the smallest positive integer with no double-base representation of length $ 2$, that $ 4985$ is the smallest positive integer with no double-base representation of length $ 3$, that $ 641687$ is the smallest positive integer with no double-base representation of length $ 4$, and that $ 326552783$ is the smallest positive integer with no double-base representation of length $ 5$.


References [Enhancements On Off] (What's this?)

  • 1. Zs. Ádám, L. Hajdu, and F. Luca, Representing integers as linear combinations of $ S$-units, Acta Arith. 138 (2009), no. 2, 101-107. MR 2520130 (2010d:11041)
  • 2. Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), no. 1, 173-206. MR 683806 (84e:10008)
  • 3. Roberto Avanzi, Vassil Dimitrov, Christophe Doche, and Francesco Sica, Extending scalar multiplication using double bases, Advances in cryptology--ASIACRYPT 2006, Lecture Notes in Comput. Sci., vol. 4284, Springer, Berlin, 2006, pp. 130-144. MR 2444632 (2009h:11092)
  • 4. Valérie Berthé and Laurent Imbert, Diophantine approximation, Ostrowski numeration and the double-base number system, Discrete Math. Theor. Comput. Sci. 11 (2009), no. 1, 153-172. MR 2500701 (2010a:11015)
  • 5. Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235-265, Computational algebra and number theory (London, 1993). MR 1484478
  • 6. V. S. Dimitrov, G. A. Jullien, and W. C. Miller, An algorithm for modular exponentiation, Inform. Process. Lett. 66 (1998), no. 3, 155-159. MR 1627991 (99d:94023)
  • 7. Vassil Dimitrov, Laurent Imbert, and Pradeep K. Mishra, The double-base number system and its application to elliptic curve cryptography, Math. Comp. 77 (2008), no. 262, 1075-1104. MR 2373193 (2009c:94044)
  • 8. Vassil Dimitrov, Laurent Imbert, and Pradeep Kumar Mishra, Efficient and secure elliptic curve point multiplication using double-base chains, Advances in cryptology--ASIACRYPT 2005, Lecture Notes in Comput. Sci., vol. 3788, Springer, Berlin, 2005, pp. 59-78. MR 2236727 (2007k:94071)
  • 9. Christophe Doche and Laurent Imbert, Extended double-base number system with applications to elliptic curve cryptography, Progress in cryptology--INDOCRYPT 2006, Lecture Notes in Comput. Sci., vol. 4329, Springer, Berlin, 2006, pp. 335-348. MR 2454920 (2009j:94105)
  • 10. W. J. Ellison, On a theorem of S. Sivasankaranarayana Pillai, Séminaire de Théorie des Nombres, 1970-1971 (Univ. Bordeaux I, Talence), Exp. No. 12, Lab. Théorie des Nombres, Centre Nat. Recherche Sci., Talence, 1971. MR 0417051 (54:5112)
  • 11. Paul Erdős, Carl Pomerance, and Eric Schmutz, Carmichael's lambda function, Acta Arith. 58 (1991), no. 4, 363-385. MR 1121092 (92g:11093)
  • 12. Pradeep Kumar Mishra and Vassil Dimitrov, A combinatorial interpretation of double base number system and some consequences, Adv. Math. Commun. 2 (2008), no. 2, 159-173. MR 2403045 (2009d:94097)
  • 13. K. W. Wong, Edward C. W. Lee, L. M. Cheng, and Xiaofeng Liao, Fast elliptic scalar multiplication using new double-base chain and point halving, Appl. Math. Comput. 183 (2006), no. 2, 1000-1007. MR 2290854
  • 14. ChangAn Zhao, FangGuo Zhang, and JiWu Huang, Efficient Tate pairing computation using double-base chains, Sci. China Ser. F 51 (2008), no. 8, 1096-1105. MR 2420846 (2009h:94156)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 11A67, 11A63

Retrieve articles in all journals with MSC (2010): 11A67, 11A63


Additional Information

Vassil S. Dimitrov
Affiliation: Center for Information Security and Cryptography, University of Calgary, 2500 University Drive NW, Calgary, AB T2N 1N4, Canada
Email: dimitrov@atips.ca

Everett W. Howe
Affiliation: Center for Communications Research, 4320 Westerra Court, San Diego, California 92121-1967
Email: however@alumni.caltech.edu

DOI: https://doi.org/10.1090/S0002-9939-2011-10764-0
Received by editor(s): August 27, 2010
Published electronically: February 9, 2011
Communicated by: Ken Ono
Article copyright: © Copyright 2011 American Mathematical Society and the Institute for Defense Analyses

American Mathematical Society