ГлавнаяАрхивУточнение нижней оценки сложности возведения в степень

Уточнение нижней оценки сложности возведения в степень | Прикладная дискретная математика. 2017. № 38. DOI: 10.17223/20710410/38/10

Для величины l(xn) -минимального числа операций умножения, достаточного для вычисления по переменной x степени xn - уточнена нижняя оценка. Установлено, что для любого е > 0 доля чисел к, не превосходящих n и удовлетворяющих условию l(xk) > log2 n + стремится к 1 при n ^ те. log2 n log2 log2 n 1 - (2 + е) log2log2log2 n log2log2 n
  • Title Уточнение нижней оценки сложности возведения в степень
  • Headline Уточнение нижней оценки сложности возведения в степень
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 38
  • Date:
  • DOI 10.17223/20710410/38/10
Ключевые слова
аддитивные цепочки, возведение в степень, нижние оценки сложности, addition chains, exponentiation, lower bounds of complexity
Авторы
Ссылки
Кнут Д. Е. Искусство программирования. Т. 2. 3-е изд. М.: Издательский дом «Вильямс», 2000.
Scholz A. Jahresbericht // Deutsche Mathematiker-Vereinigung. 1937. B.47. S. 41-42.
Subbarao M. V. Addition chains - some results and problems // Number Theory and Applications / ed. R. A. Mollin. NATO Advanced Science Institutes Series: Ser. C. Kluwer Academic Publisher Group, 1989. V. 265. P. 555-574.
Bos J. and Coster M. Addition chain heuristics // Crypto’89. LNCS. 1990. V. 435. P. 400-407. Gordon D. M. A survey of fast exponentiation methods // J. Algorithms. 1998. V. 27. P. 129-146
Thurber E. G. Efficient generation of minimal length addition chains // SIAM J. Comput. 1999. V.28. P.1247-1263
Bernstein D. J. Pippenger’s exponentiation algorithm. http://cr.yp.to/papers/ pippenger.pdf, 2002
Гашков С. Б. Задача об аддитивных цепочках и ее обобщения // Математическое просвещение. Третья серия. Вып. 15. М.: МЦНМО, 2011. С. 138-153
Clift N. M. Calculating optimal addition chains // Computing. 2011. V.91. P.265-284.
Кочергин В. В. Уточнение оценок сложности вычисления одночленов и наборов степеней в задачах Беллмана и Кнута // Дискретный анализ и исследование операций. 2014. Т. 21. №6. С. 51-72
Jarvinen K, Dimitrov V., and Azarderakhsh R. A generalization of addition chains and fast inversions in binary fields // IEEE Trans. Computers. 2015. V. 64(9). P.2421-2432
Von zur Gathen J. and Nocker M. Exponentiation in finite fields: theory and practice // LNCS. 1997. V. 1255. P.88-113
Смарт Н. Криптография. М.: Техносфера, 2005
Гашков С. Б., Сергеев И. С. О применении метода аддитивных цепочек к инвертированию в конечных полях // Дискретная математика. 2006. Т. 18. №4. С. 56-72
Brauer A. On addition chains // Bull. Amer. Math. Soc. 1939. V. 45. P.736-739
16. Erdos P. Remarks on number theory, III: On addition chains // Acta Arith. 1960. V. 6. P. 77-81
Ильин А. М. Об аддитивных цепочках чисел // Проблемы кибернетики. Вып. 13. М.: Физматлит, 1965. С. 245-248
Schonhage A. A. Lower bound for the length of addition chains // Theor. Comput. Sci. 1975. V. 1. P. 1-12
Сэвидж Д. Е. Сложность вычислений. М.: Факториал, 1998.
Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991.
Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.
Riordan J. and Shannon C. E. The number of two-terminal series-parallel networks // J. Math. Phys. Mass. Inst. Tech. 1942. V. 21. No. 2. P. 83-93. Рус. пер.: Риодан Дж., Шеннон К. Число двухполюсных параллельно-последовательных сетей / сб. Шеннон К. Работы по теории информации и кибернетике. М.: ИЛ, 1963. С. 46-58.
Ложкин С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов // Математические вопросы кибернетики. Вып. 6. М.: Наука, 1996. С. 189-214.
Ложкин С. А. Асимптотические оценки высокой степени точности для сложности реализации булевских функций схемами из функциональных элементов // Труды II Междунар. конф. «Дискретные модели в теории управляющих систем» (23-28 июня 1997 г.). М.: Диалог-МГУ, 1997. С. 37-39.
Кочергин В. В., Кочергин Д. В. Уточнение асимптотического поведения сложности сборки слов схемами конкатенации // Вестн. Моск. ун-та. Сер. 1. Матем. Механ. 2016. №2. С. 12-18.
Volger H. Some results on addition/subtraction chains // Inform. Proc. Lett. 1985. V. 20. P. 155-160.
Morain F. and Olivos J. Speeding up the computation on an elliptic curve using addition-subtraction chains // Informatique Theorique et Applications. 1990. V. 24. P. 531-544.
Кочергин В. В. О сложности вычислений одночленов и наборов степеней // Дискретный анализ. Новосибирск: Изд-во Института математики СО РАН, 1994. С. 94-107.
Уточнение нижней оценки сложности возведения в степень | Прикладная дискретная математика. 2017. № 38. DOI: 10.17223/20710410/38/10
Уточнение нижней оценки сложности возведения в степень | Прикладная дискретная математика. 2017. № 38. DOI: 10.17223/20710410/38/10