Non-minimality of the width-𝑤 non-adjacent form in conjunction with trace one 𝜏-adic digit expansions and Koblitz curves in characteristic two

Krenn, Daniel; Ziegler, Volker

doi:10.1090/mcom/3227

Non-minimality of the width-$w$ non-adjacent form in conjunction with trace one $\tau$-adic digit expansions and Koblitz curves in characteristic two
HTML articles powered by AMS MathViewer

by Daniel Krenn and Volker Ziegler PDF

Math. Comp. 87 (2018), 821-854 Request permission

Abstract:

This article deals with redundant digit expansions with an imaginary quadratic algebraic integer with trace $\pm 1$ as base and a minimal norm representatives digit set. For $w\geq 2$ it is shown that the width-$w$ non-adjacent form is not an optimal expansion, meaning that it does not minimize the (Hamming) weight among all possible expansions with the same digit set. One main part of the proof uses tools from Diophantine analysis, namely the theory of linear forms in logarithms and the Baker–Davenport reduction method.

References

Roberto Maria Avanzi, A note on the signed sliding window integer recoding and a left-to-right analogue, Selected areas in cryptography, Lecture Notes in Comput. Sci., vol. 3357, Springer, Berlin, 2005, pp. 130–143. MR 2180673, DOI 10.1007/978-3-540-30564-4_{9}
Roberto Maria Avanzi, Clemens Heuberger, and Helmut Prodinger, Minimality of the Hamming weight of the $\tau$-NAF for Koblitz curves and improved combination with point halving, Selected areas in cryptography, Lecture Notes in Comput. Sci., vol. 3897, Springer, Berlin, 2006, pp. 332–344. MR 2241647, DOI 10.1007/11693383_{2}3
Roberto M. Avanzi, Clemens Heuberger, and Helmut Prodinger, Scalar multiplication on Koblitz curves using the Frobenius endomorphism and its combination with point halving: extensions and mathematical analysis, Algorithmica 46 (2006), no. 3-4, 249–270. MR 2291956, DOI 10.1007/s00453-006-0105-9
Roberto Avanzi, Clemens Heuberger, and Helmut Prodinger, Redundant $\tau$-adic expansions I: non-adjacent digit sets and their applications to scalar multiplication, Des. Codes Cryptogr. 58 (2011), no. 2, 173–202. MR 2770310, DOI 10.1007/s10623-010-9396-6
A. Baker and H. Davenport, The equations $3x^{2}-2=y^{2}$ and $8x^{2}-7=z^{2}$, Quart. J. Math. Oxford Ser. (2) 20 (1969), 129–137. MR 248079, DOI 10.1093/qmath/20.1.129
I. F. Blake, G. Seroussi, and N. P. Smart, Elliptic curves in cryptography, London Mathematical Society Lecture Note Series, vol. 265, Cambridge University Press, Cambridge, 2000. Reprint of the 1999 original. MR 1771549
J. W. S. Cassels, An introduction to the geometry of numbers, Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen mit besonderer Berücksichtigung der Anwendungsgebiete, Bd. 99, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1959. MR 0157947
Daniel M. Gordon, A survey of fast exponentiation methods, J. Algorithms 27 (1998), no. 1, 129–146. MR 1613189, DOI 10.1006/jagm.1997.0913
Clemens Heuberger, Redundant $\tau$-adic expansions. II. Non-optimality and chaotic behaviour, Math. Comput. Sci. 3 (2010), no. 2, 141–157. MR 2608292, DOI 10.1007/s11786-009-0014-9
Clemens Heuberger and Daniel Krenn, Analysis of width-$w$ non-adjacent forms to imaginary quadratic bases, J. Number Theory 133 (2013), no. 5, 1752–1808. MR 3007130, DOI 10.1016/j.jnt.2012.08.029
C. Heuberger and D. Krenn, Existence and optimality of $w$-non-adjacent forms with an algebraic integer base, Acta Math. Hungar. 140 (2013), no. 1-2, 90–104. MR 3123865, DOI 10.1007/s10474-013-0303-2
Clemens Heuberger and Daniel Krenn, Optimality of the width-$w$ non-adjacent form: general characterisation and the case of imaginary quadratic bases, J. Théor. Nombres Bordeaux 25 (2013), no. 2, 353–386 (English, with English and French summaries). MR 3228312
J. Jedwab and C. J. Mitchell, Minimum weight modified signed-digit representations and fast exponentiation, Electron. Lett. 25 (1989), 1171–1172.
Neal Koblitz, CM-curves with good cryptographic properties, Advances in cryptology—CRYPTO ’91 (Santa Barbara, CA, 1991) Lecture Notes in Comput. Sci., vol. 576, Springer, Berlin, 1992, pp. 279–287. MR 1243654, DOI 10.1007/3-540-46766-1_{2}2
Neal Koblitz, An elliptic curve implementation of the finite field digital signature algorithm, Advances in cryptology—CRYPTO ’98 (Santa Barbara, CA, 1998) Lecture Notes in Comput. Sci., vol. 1462, Springer, Berlin, 1998, pp. 327–337. MR 1670960, DOI 10.1007/BFb0055739
E. M. Matveev, An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers. II, Izv. Ross. Akad. Nauk Ser. Mat. 64 (2000), no. 6, 125–180 (Russian, with Russian summary); English transl., Izv. Math. 64 (2000), no. 6, 1217–1269. MR 1817252, DOI 10.1070/IM2000v064n06ABEH000314
Willi Meier and Othmar Staffelbach, Efficient multiplication on certain nonsupersingular elliptic curves, Advances in cryptology—CRYPTO ’92 (Santa Barbara, CA, 1992) Lecture Notes in Comput. Sci., vol. 740, Springer, Berlin, 1993, pp. 333–344. MR 1287863, DOI 10.1007/3-540-48071-4_{2}4
A. Miyaji, T. Ono, and H. Cohen, Efficient elliptic curve exponentiation, Information and Communications Security. 1st International Conference, ICICS ’97, Beijing, China, November 11–14, 1997. Proceedings (Yongfei Han, Tatsuaki Okamoto, and Sihan Qing, eds.), Lecture Notes in Comput. Sci., vol. 1334, Springer-Verlag, 1997, pp. 282–290.
James A. Muir and Douglas R. Stinson, Minimality and other properties of the width-$w$ nonadjacent form, Math. Comp. 75 (2006), no. 253, 369–384. MR 2176404, DOI 10.1090/S0025-5718-05-01769-2
A. Pethö and B. M. M. de Weger, Products of prime powers in binary recurrence sequences. I. The hyperbolic case, with an application to the generalized Ramanujan-Nagell equation, Math. Comp. 47 (1986), no. 176, 713–727. MR 856715, DOI 10.1090/S0025-5718-1986-0856715-5
B. Phillips and N. Burgess, Minimal weight digit set conversions, IEEE Trans. Comput. 53 (2004), 666–677.
George W. Reitwiesner, Binary arithmetic, Advances in Computers, Vol. 1, Academic Press, New York, 1960, pp. 231–308. MR 0122018
Paulo Ribenboim, Classical theory of algebraic numbers, Universitext, Springer-Verlag, New York, 2001. MR 1821363, DOI 10.1007/978-0-387-21690-4
The SageMath Developers, SageMath Mathematics Software (Version 7.0), 2016, http://www.sagemath.org.
J. A. Solinas, An improved algorithm for arithmetic on a family of elliptic curves, Advances in Cryptology — CRYPTO ’97. 17th Annual International Cryptology Conference, Santa Barbara, CA, August 17–21, 1997. Proceedings (B. S. Kaliski, ed.), Lecture Notes in Comput. Sci., vol. 1294, Springer, Berlin, 1997, pp. 357–371.
Jerome A. Solinas, Efficient arithmetic on Koblitz curves, Des. Codes Cryptogr. 19 (2000), no. 2-3, 195–249. Towards a quarter-century of public key cryptography. MR 1759617, DOI 10.1023/A:1008306223194