Existence and optimality of \(w\)-non-adjacent forms with an algebraic integer base. (English) Zbl 1289.11004
The authors consider digit expansions in lattices with endomorphisms acting as base. In particular, they focus upon the \(w\)-non-adjacent form (\(w\)-NAF) with the property that each block of \(w\) consecutive digits contains at most one non-zero digit. They prove that for sufficiently large \(w\), and an expanding endomorphism, there exists a suitable digit such that each lattice element has an expansion as a \(w\)-NAF. Under certain conditions they are able to establish that the \(w\)-NAF minimizes the weight among all possible expansions of the same lattice element employing the same digit system.
Reviewer: Richard A. Mollin (Calgary)
MSC:
| 11A63 | Radix representation; digital problems |
| 11H06 | Lattices and convex bodies (number-theoretic aspects) |
| 11R04 | Algebraic numbers; rings of algebraic integers |
| 94A60 | Cryptography |
Keywords:
\(\tau\)-adic expansion; \(w\)-non-adjacent form; redundant digit set; lattice; existence; hyperelliptic curve cryptography; Koblitz curve; Frobenius endomorphism; scalar multiplication; Hamming weight; optimality; minimal expansionReferences:
| [1] | Avanzi, R. M.; Handschuh, H. (ed.); Hasan, A. (ed.), A note on the signed sliding window integer recoding and a left-to-right analogue, SAC 2004, Waterloo, Canada, August 9-10, 2004, Berlin · Zbl 1117.94007 · doi:10.1007/978-3-540-30564-4_9 |
| [2] | I. F. Blake, V. K. Murty and G. Xu, Efficient algorithms for Koblitz curves over fields of characteristic three, J. Discrete Algorithms, 3 (2005), 113-124. · Zbl 1070.11056 · doi:10.1016/j.jda.2004.04.011 |
| [3] | I. F. Blake, V. K. Murty and G. Xu, A note on window τ-NAF algorithm, Inform. Process. Lett., 95 (2005), 496-502. · Zbl 1182.94037 · doi:10.1016/j.ipl.2005.05.013 |
| [4] | I. F. Blake, V. K. Murty and G. Xu, Nonadjacent radix-τ expansions of integers in Euclidean imaginary quadratic number fields, Canad. J. Math., 60 (2008), 1267-1282. · Zbl 1228.11160 · doi:10.4153/CJM-2008-054-1 |
| [5] | P. Deligne, La conjecture de Weil. I, Inst. Hautes Études Sci. Publ. Math., 43 (1974), 273-307. · Zbl 0287.14001 · doi:10.1007/BF02684373 |
| [6] | B. Dwork, On the rationality of the zeta function of an algebraic variety, Amer. J. Math., 82 (1960), 631-648. · Zbl 0173.48501 · doi:10.2307/2372974 |
| [7] | L. Germán and A. Kovács, On number system constructions, Acta Math. Hungar., 115 (2007), 155-167. · Zbl 1153.11003 · doi:10.1007/s10474-007-5224-5 |
| [8] | C. Heuberger and D. Krenn, Optimality of the width-w non-adjacent form: General characterisation and the case of imaginary quadratic bases, to appear in J. Théor. Nombres Bordeaux (2013), earlier version available at arXiv:1110.0966v1 [math.NT] (2011). · Zbl 1282.11005 |
| [9] | C. Heuberger and D. Krenn, Analysis of width-w non-adjacent forms to imaginary quadratic bases, to appear in J. Number Theory (2012), earlier version available at arXiv:1009.0488v2 [math.NT]. · Zbl 1300.11013 |
| [10] | B. Kovács and A. Pethő, Number systems in integral domains, especially in orders of algebraic number fields, Acta Sci. Math. (Szeged), 55 (1991), 287-299. · Zbl 0760.11002 |
| [11] | J. A. Muir and D. R. Stinson, Alternative digit sets for nonadjacent representations, SIAM J. Discrete Math., 19 (2005), 165-191. · Zbl 1122.11005 · doi:10.1137/S0895480103437651 |
| [12] | Solinas, J. A.; Kaliski, B. S. (ed.), An improved algorithm for arithmetic on a family of elliptic curves, Santa Barbara, CA, USA, August 17-21, 1997, Berlin · Zbl 1032.11062 · doi:10.1007/BFb0052248 |
| [13] | J. A. Solinas, Efficient arithmetic on Koblitz curves, Des. Codes Cryptogr., 19 (2000), 195-249. · Zbl 0997.94017 · doi:10.1023/A:1008306223194 |
| [14] | A. Vince, Replicating tessellations, SIAM J. Discrete Math., 6 (1993), 501-521. · Zbl 0826.52019 · doi:10.1137/0406040 |
| [15] | A. Weil, Variétés abéliennes et courbes algébriques, Actualités scientifiques et industrielles 1064, Hermann & Cie (1948). · Zbl 0037.16202 |
| [16] | A. Weil, Numbers of solutions of equations in finite fields, Bull. Amer. Math. Soc., 55 (1949), 497-508. · Zbl 0032.39402 · doi:10.1090/S0002-9904-1949-09219-4 |
| [17] | A. Weil, Courbes algébriques et variétés abéliennes, Hermann (1971). · Zbl 0208.49202 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
