О схемах для арифметики в конечных полях
Автор: Бурцев Алексей Анатольевич, Гашков Сергей Борисович
Журнал: Труды Московского физико-технического института @trudy-mipt
Статья в выпуске: 4 (16) т.4, 2012 года.
Бесплатный доступ
В работе доказывается, что для любого ɛ> 0 при любом m, n = ms и s ≥ sɛ можно выбрать в поле GF(2n) базис, для которого схемная сложность умножения меньше n1+ɛ/2, а сложность инвертирования меньше n+ɛ. При n = 2 · 3k в некотором базисе получены оценки сложности умножения n(log3n)(log2 log3 n)/2+O(1), и по порядку такие же оценки получены для инвертирования.
Булевы схемы, сложность схем, арифметика, конечные поля
Короткий адрес: https://sciup.org/142185866
IDR: 142185866
Список литературы О схемах для арифметики в конечных полях
- Gathen J. von zur, Gerhard J. Modern computer algebra. -Cambridge University Press, 1999.
- Schonhage A. Schnelle Multiplication von Polynomen.uber K.orpern der Charakteristik 2//Acta Informatica. -1977. -V. 7. -P. 395-398.
- Schonhage A. Schnelle berechnung von kettenbruchentwicklungen//Acta Informatica 1. -1971. -P. 139-144.
- Gao S., Gathen J. von zur, Panario D., Shoup V. Algorithm for exponentiation in finite field//J. of Symbolic Computation. -2000. -V. 29. -P. 879-889.
- Штрассен Ф. Алгоритм Гаусса не оптимален//Кибернетический сборник. -Вып. 7. -М.: Мир, 1971.
- Болотов А.А., Гашков С.Б. О быстром умножении в нормальных базисах конечных полей//Дискретная математика. -2001. -Т. 13, № 3. -С. 3-31.
- Itoh T., Tsujii S. A fast algorithm for computing multiplicative inverses in GF(2n) using normal bases//Inform. And Comp. -1988. -V. 78. -P. 171-177.
- Кнут Д. Искусство программирования. Т. 2. -2-е изд. -М.: Вильямс, 2000.
- Gathen J. von zur, N.ocker M. Fast arithmetic with general Gauss periods//Theor. Comp. Sci. -2004. -V. 315. -P. 419-452.
- Paar C., Fan J.L. Efficient inversion in tower fields of characteristic two. -ISIT, Ulm, Germany, 1997.
- Гашков С.Б. Замечания о быстром умножении многочленов, преобразовании Фурье и Хартли//Дискретная математика. -2000. -Т. 12, № 3. -С. 124-153.
- Лидл Р., Hидеppейтеp Х. Конечные поля. -М.: Миp, 1988.
Статья научная
