Geodesic
Improvement of the lower bound for the complexity of exponentiation
Prikladnaâ diskretnaâ matematika, no. 4 (2017), pp. 119-132.

Voir la notice de l'article provenant de la source Math-Net.Ru

Let $l(x^n)$ be the minimal number of multiplications sufficient for computing $x^n$. In the paper, we improve the lower bound of $l(x^n)$. We establish that for all $\varepsilon >0$ the fraction of the numbers $k$, $k\le n$, satisfying the relation \begin{equation*} l(x^k)>\log_2n+\frac{\log_2n}{\log_2\log_2n}\left(1-(2+\varepsilon)\frac{\log_2\log_2\log_2n}{\log_2\log_2n}\right), \end{equation*} tends to 1 as $n\to\infty$.
Mots-clés : addition chains
Keywords: exponentiation, lower bounds of complexity. 
@article{PDM_2017_4_a9,
     author = {V. V. Kochergin and D. V. Kochergin},
     title = {Improvement of the lower bound for the complexity of  exponentiation},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {119--132},
     publisher = {mathdoc},
     number = {4},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2017_4_a9/}
}
TY  - JOUR
AU  - V. V. Kochergin
AU  - D. V. Kochergin
TI  - Improvement of the lower bound for the complexity of  exponentiation
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2017
SP  - 119
EP  - 132
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2017_4_a9/
LA  - ru
ID  - PDM_2017_4_a9
ER  - 
%0 Journal Article
%A V. V. Kochergin
%A D. V. Kochergin
%T Improvement of the lower bound for the complexity of  exponentiation
%J Prikladnaâ diskretnaâ matematika
%D 2017
%P 119-132
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2017_4_a9/
%G ru
%F PDM_2017_4_a9
V. V. Kochergin; D. V. Kochergin. Improvement of the lower bound for the complexity of  exponentiation. Prikladnaâ diskretnaâ matematika, no. 4 (2017), pp. 119-132. http://geodesic.mathdoc.fr/item/PDM_2017_4_a9/

[1] Knuth D. E., The art of computer programming, v. 2, third edition, Addison-Wesley, Reading, Massachusetts, 1998 | MR | MR | Zbl

[2] Scholz A., “Jahresbericht”, Deutsche Mathematiker-Vereinigung, 47 (1937), 41–42

[3] Subbarao M. V., “Addition chains – some results and problems”, Number Theory and Applications, NATO Advanced Science Institutes Series: Ser. C, 265, ed. R. A. Mollin, Kluwer Academic Publisher Group, 1989, 555–574 | MR

[4] Bos J., Coster M., “Addition chain heuristics”, Crypto'89, LNCS, 435, 1990, 400–407

[5] Gordon D. M., “A survey of fast exponentiation methods”, J. Algorithms, 27 (1998), 129–146 | DOI | MR | Zbl

[6] Thurber E. G., “Efficient generation of minimal length addition chains”, SIAM J. Comput., 28 (1999), 1247–1263 | DOI | MR | Zbl

[7] Bernstein D. J., Pippenger's exponentiation algorithm, , 2002 http://cr.yp.to/papers/pippenger.pdf

[8] Gashkov S. B., “Addition chains problem and its generalizations”, Matematicheskoye Prosveshcheniye. Third series, 15, MTsNMO, Moscow, 2011, 138–153 (in Russian)

[9] Clift N. M., “Calculating optimal addition chains”, Computing, 91 (2011), 265–284 | DOI | MR | Zbl

[10] Kochergin V. V., “Improvement of the estimates of the computational complexity for monomials and sets of powers in Bellman's and Knuth's problems”, J. Appl. Industr. Math., 9:1 (2015), 68–82 | DOI | MR | Zbl

[11] Järvinen K., Dimitrov V., Azarderakhsh R., “A generalization of addition chains and fast inversions in binary fields”, IEEE Trans. Computers, 64:9 (2015), 2421–2432 | DOI | MR | Zbl

[12] Von zur Gathen J., Nocker M., “Exponentiation in finite fields: theory and practice”, LNCS, 1255, 1997, 88–113 | MR | Zbl

[13] Smart N., Cryptography: An Introduction, 3rd edition, McGraw – Hill, 2003

[14] Gashkov S. B., Sergeev I. S., “An application of the method of additive chains to inversion in finite fields”, Discr. Math. Appl., 16:6 (2006), 601–618 | DOI | DOI | MR | Zbl

[15] Brauer A., “On addition chains”, Bull. Amer. Math. Soc., 45 (1939), 736–739 | DOI | MR | Zbl

[16] Erdos P., “Remarks on number theory, III: On addition chains”, Acta Arith., 6 (1960), 77–81 | DOI | MR | Zbl

[17] Il'in A. M., “On addition chains of numbers”, Problemy Kibernetiki, 13, Fizmatlit Publ., Moscow, 1965, 245–248 (in Russian)

[18] Schönhage A. A., “Lower bound for the length of addition chains”, Theor. Comput. Sci., 1 (1975), 1–12 | DOI | MR | Zbl

[19] Savage J. E., The Complexity of Computing, Wiley, New York, 1976 | MR | Zbl

[20] Nigmatullin R. G., The Complexity of Boolean Functions, Nauka Publ., Moscow, 1991 (in Russian) | MR

[21] Lupanov O. B., Asymptotic Estimations of Complexity of Control Systems, MSU Publ., Moscow, 1984 (in Russian)

[22] Riordan J., Shannon C. E., “The number of two-terminal series-parallel networks”, J. Math. Phys. Mass. Inst. Tech., 21:2 (1942), 83–93 ; Riodan Dzh., Shennon K., “Chislo dvukhpolyusnykh parallelno-posledovatelnykh setei”: Shennon K., Raboty po teorii informatsii i kibernetike, Sb., IL, M., 1963, 46–58 | MR

[23] Lozhkin S. A., “More accurate estimations of complexity of control systems for some classes”, Matematicheskiye Voprosy Kibernetiki, 6, Nauka Publ., Moscow, 1996, 189–214 (in Russian) | MR

[24] Lozhkin S. A., “More accurate asymptotic estimations of complexity of Boolean functions realization by logic circuits”, Proc. II Intern. conf. “Diskretnye modeli v teorii upravlyayushchikh sistem” (22–23 June 1997), Dialog-MSU Publ., Moscow, 1997, 37–39 (in Russian)

[25] Kochergin V. V., Kochergin D. V., “Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits”, Moscow University Math. Bull., 71:2 (2016), 55–60 | DOI | MR | Zbl

[26] Volger H., “Some results on addition/subtraction chains”, Inform. Proc. Lett., 20 (1985), 155–160 | DOI | MR | Zbl

[27] Morain F., Olivos J., “Speeding up the computation on an elliptic curve using addition-subtraction chains”, Informatique Théorique et Applications, 24 (1990), 531–544 | DOI | MR

[28] Kochergin V. V., “On the complexity of computations of monomials and tuples of powers.”, Siberian Adv. Math., 6:1 (1996), 71–86 | MR