×

zbMATH — the first resource for mathematics

Lower bounds on the lengths of double-base representations. (English) Zbl 1263.11086
Summary: 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.

MSC:
11N56 Rate of growth of arithmetic functions
11A63 Radix representation; digital problems
11A67 Other number representations
Software:
Magma
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Zs. Ádám, L. Hajdu, and F. Luca, Representing integers as linear combinations of \?-units, Acta Arith. 138 (2009), no. 2, 101 – 107. · Zbl 1230.11044 · doi:10.4064/aa138-2-1 · doi.org
[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. · Zbl 0526.10004 · doi:10.2307/2006975 · doi.org
[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. · Zbl 1172.94558 · doi:10.1007/11935230_9 · doi.org
[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. · Zbl 1221.11017
[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). · Zbl 0898.68039 · doi:10.1006/jsco.1996.0125 · doi.org
[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. · Zbl 1078.94510 · doi:10.1016/S0020-0190(98)00044-1 · doi.org
[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. · Zbl 1133.14034
[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. · Zbl 1154.94388 · doi:10.1007/11593447_4 · doi.org
[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. · Zbl 1175.94076 · doi:10.1007/11941378_24 · doi.org
[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, pp. 10. · Zbl 0276.10012
[11] Paul Erdős, Carl Pomerance, and Eric Schmutz, Carmichael’s lambda function, Acta Arith. 58 (1991), no. 4, 363 – 385. · Zbl 0734.11047
[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. · Zbl 1178.05008 · doi:10.3934/amc.2008.2.159 · doi.org
[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. · Zbl 1126.94015 · doi:10.1016/j.amc.2006.05.111 · doi.org
[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. · Zbl 1210.94098 · doi:10.1007/s11432-008-0070-9 · doi.org
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.