Оптимальные нормальные базисы 2-го и 3-го типов в конечных полях характеристики семь
Ключевые слова:
конечное поле, полиномиальный и оптимальный нормальный базисы, преобразование базисов, характеристика поля, конечное поле характеристики семь, возведение в степень, умножение, обращение, гиперэллиптическая кривая, спаривание Тейта
Аннотация
Рассмотрены оптимальные нормальные базисы 2-го и 3-го типов и их модификации для имплементации арифметических операций в конечных полях характеристики семь. Описаны представления элементов данных полей в базисах подобных типов: переставленном, приведенном (редуцированном), редундантном, а также полиномиальном. Представлены алгоритмы преобразования между указанными представлениями и алгоритмы умножения с использованием полиномиального базиса, возведения в степень, равной степени характеристики поля, обращения и возведения в произвольную степень.
Литература
1. Лидл. Р., Нидеррайтер Г. Конечные поля. Т. 1, 2. М.: Мир, 1988.
2. Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы. М.: КомКнига, 2012.
3. Mullin R.C., Onyszchuk I.M.,Vanstone S.A., Wilson R.M. Optimal Normal Bases in GF(pn) // Discrete Appl. Math. 1988 89). 22, 149-161.
4. Болотов А.А., Гашков С.Б. О быстром умножении в нормальных базисах конечных полей // Дискретная математика. 2001. Т. 13. Вып. 3. С. 3 — 31.
5. Shokrollahi J. Efficient implementation of elliptic curve cryptography on FPGA: PhD thesis. Universitet Bonn, 2007.
6. Gathen von zur J., Shokrollahi A., Shokrollahi J. Efficient multiplication using type 2 optimal normal bases. // Proc. WAIFI 07, LNCS. 2007. P. 55 — 68.
7. Bernstein D.J., Lange T. Type-II Optimal Polynomial Bases, Arithmetic of Finite Fields // Proc. LNCS, 6087. 2010. P. 41 — 61.
8. Gashkov S., Frolov A., Lukin S., Sukhanova O. Arithmetic in the finite fields using optimal normal and polynomial bases in combination // Advances in Intelligent Systems and Computing. 2015. P. 153 — 162.
9. Koblitz N. Algebraic aspects of Cryptography. Berlin Heidelberg: Springer Verlag, 1998.
10. Koblitz N., Menezes A. Pairing-based cryptography at high security levels // Proc.Tenth IMA Intern. conf. cryptography and coding. 2005. P. 3 — 36.
11. Гашков С.Б. и др. О схемной и программной реализации арифметики в конечных полях характеристики 7 для вычисления спариваний // Фундаментальная и прикладная математика. 2009. № 3. C. 75 — 111.
12. Гашков С.Б., Фролов А.Б., Шилкин С.О. О некоторых алгоритмах обращения и деления в конечных кольцах и полях // Вестник МЭИ. 2006. № 6. С. 20 — 31.
13. Hankerson D., López J.H., Menezes A. Software implementation of elliptic curve cryptography over binary fields. CHES 2000 // LNCS. 2000. N 1965. P. 1 — 23.
2. Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы. М.: КомКнига, 2012.
3. Mullin R.C., Onyszchuk I.M.,Vanstone S.A., Wilson R.M. Optimal Normal Bases in GF(pn) // Discrete Appl. Math. 1988 89). 22, 149-161.
4. Болотов А.А., Гашков С.Б. О быстром умножении в нормальных базисах конечных полей // Дискретная математика. 2001. Т. 13. Вып. 3. С. 3 — 31.
5. Shokrollahi J. Efficient implementation of elliptic curve cryptography on FPGA: PhD thesis. Universitet Bonn, 2007.
6. Gathen von zur J., Shokrollahi A., Shokrollahi J. Efficient multiplication using type 2 optimal normal bases. // Proc. WAIFI 07, LNCS. 2007. P. 55 — 68.
7. Bernstein D.J., Lange T. Type-II Optimal Polynomial Bases, Arithmetic of Finite Fields // Proc. LNCS, 6087. 2010. P. 41 — 61.
8. Gashkov S., Frolov A., Lukin S., Sukhanova O. Arithmetic in the finite fields using optimal normal and polynomial bases in combination // Advances in Intelligent Systems and Computing. 2015. P. 153 — 162.
9. Koblitz N. Algebraic aspects of Cryptography. Berlin Heidelberg: Springer Verlag, 1998.
10. Koblitz N., Menezes A. Pairing-based cryptography at high security levels // Proc.Tenth IMA Intern. conf. cryptography and coding. 2005. P. 3 — 36.
11. Гашков С.Б. и др. О схемной и программной реализации арифметики в конечных полях характеристики 7 для вычисления спариваний // Фундаментальная и прикладная математика. 2009. № 3. C. 75 — 111.
12. Гашков С.Б., Фролов А.Б., Шилкин С.О. О некоторых алгоритмах обращения и деления в конечных кольцах и полях // Вестник МЭИ. 2006. № 6. С. 20 — 31.
13. Hankerson D., López J.H., Menezes A. Software implementation of elliptic curve cryptography over binary fields. CHES 2000 // LNCS. 2000. N 1965. P. 1 — 23.
Опубликован
2018-12-03
Выпуск
Раздел
Информатика, вычислительная техника и управление (05.13.00)
