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 is an expression , where the are (positive or negative) integers that are divisible by no primes other than or ; the *length* of the representation is the number of terms. It is known that there is a constant such that every integer has a double-base representation of length at most . We show that there is a constant such that there are infinitely many integers whose shortest double-base representations have length greater than .

Our methods allow us to find the smallest positive integers with no double-base representations of several lengths. In particular, we show that is the smallest positive integer with no double-base representation of length , that is the smallest positive integer with no double-base representation of length , that is the smallest positive integer with no double-base representation of length , and that is the smallest positive integer with no double-base representation of length .

**1.**Zs. Ádám, L. Hajdu, and F. Luca,*Representing integers as linear combinations of -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)**

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