Distribution results for low-weight binary representations for pairs of integers. (English) Zbl 1050.94009
With an eye to the primary application being the group law for addition on an elliptic curve, the authors look at the computational cost of such operations in cryptosystems. In order to minimize so-called Hamming weights, they consider what is called the simple joint sparse form. This mechanism is the central focus of the paper, and is considered from geometrical and topological viewpoints, with a “central limit theorem” for the Hamming weight as one of their goals. They conclude the paper with remarks concerning the necessity for, but current lack of, a higher order analogue of the joint sparse form.
Reviewer: Richard A. Mollin (Calgary)
References:
| [1] | R. Avanzi, On the complexity of multi-exponentiation techniques in cryptography, J. Cryptology, to appear, available at; R. Avanzi, On the complexity of multi-exponentiation techniques in cryptography, J. Cryptology, to appear, available at |
| [2] | Barat, G.; Grabner, P. J., Digital functions and distribution of binomial coefficients, J. London Math. Soc., 64, 523-547 (2001) · Zbl 1049.11016 |
| [3] | Berry, A. C., The accuracy of the Gaussian approximation to the sum of independent variates, Trans. Amer. Math. Soc., 49, 122-136 (1941) · JFM 67.0461.01 |
| [4] | Booth, A. D., A signed binary multiplication technique, Quart. J. Mech. Appl. Math., 4, 236-240 (1951) · Zbl 0043.12902 |
| [5] | Delange, H., Sur les fonctions \(q\)-additive ou \(q\)-multiplicatives, Acta Arith., 21, 285-298 (1972) · Zbl 0219.10062 |
| [6] | Delange, H., Sur la fonction sommatoire de la fonction “somme des chiffres”, l’Enseignement Math. (2), 21, 31-47 (1975) · Zbl 0306.10005 |
| [7] | Esseen, C. G., Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law, Acta Math., 77, 1-125 (1945) · Zbl 0060.28705 |
| [8] | Falconer, K., Fractal geometry, Mathematical Foundations and Applications (1990), Wiley: Wiley Chichester · Zbl 0689.28003 |
| [9] | Falconer, K., Techniques in Fractal Geometry (1997), Wiley: Wiley Chichester · Zbl 0869.28003 |
| [10] | Grabner, P. J.; Rigo, M., Additive functions with respect to numeration systems on regular languages, Monatsh. Math., 139, 205-219 (2003) · Zbl 1125.11008 |
| [11] | Grabner, P. J.; Thuswaldner, J. M., On the sum of digits function for number systems with negative bases, Ramanujan J., 4, 201-220 (2000) · Zbl 0987.11007 |
| [12] | Heuberger, C.; Prodinger, H., On minimal expansions in redundant number systemsalgorithms and quantitative analysis, Computing, 66, 377-393 (2001) · Zbl 1030.11003 |
| [13] | D.E. Knuth, The art of computer programming, Seminumerical Algorithms, Vol. 2, 3rd ed. Addison-Wesley, London, 1998.; D.E. Knuth, The art of computer programming, Seminumerical Algorithms, Vol. 2, 3rd ed. Addison-Wesley, London, 1998. · Zbl 0895.65001 |
| [14] | Morain, F.; Olivos, J., Speeding up the computations on an elliptic curve using addition-subtraction chains, RAIRO Inform. Théor. Appl., 24, 531-543 (1990) · Zbl 0724.11068 |
| [15] | J.A. Solinas, Low-weight binary representations for pairs of integers, Tech. Rep. CORR 2001-41, University of Waterloo, available at; J.A. Solinas, Low-weight binary representations for pairs of integers, Tech. Rep. CORR 2001-41, University of Waterloo, available at |
| [16] | G. Tenenbaum, Sur la non-dérivabilité de fonctions périodiques associées à certaines formules sommatoires. In: R.L. Graham, J. Nešetřil (Eds.), The mathematics of Paul Erdős, I, Vol. 13, Algorithms Combin., Springer, Berlin, 1997, pp. 117-128.; G. Tenenbaum, Sur la non-dérivabilité de fonctions périodiques associées à certaines formules sommatoires. In: R.L. Graham, J. Nešetřil (Eds.), The mathematics of Paul Erdős, I, Vol. 13, Algorithms Combin., Springer, Berlin, 1997, pp. 117-128. · Zbl 0869.11019 |
| [17] | Vaaler, J. D., Some extremal functions in Fourier analysis, Bull. Amer. Math. Soc., 12, 183-216 (1985) · Zbl 0575.42003 |
| [18] | von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (1999), Cambridge University Press: Cambridge University Press New York · Zbl 0936.11069 |
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.
