OPTIMAL NORMAL BASES OF 2 AND 3 TYPES IN FINITE FIELDS OF CHARACTERISTIC 7
Keywords:
finite field, polynomial and optimal normal base, base transformation, field characteristic, finite field of characteristic, rising to power, multiplication, inversion, hyperelliptic curve, Tate pairing
Abstract
We study optimal normal bases of 2 and 3 types and their modifications for implementation of arithmetic operations in finite fields of characteristic 7. Representations of fields elements in bases of these types, permutated, reduced, redundant, polynomial base as well as transformation algorithms between those bases together with using polynomial basis multiplication algorithm, algorithms for rising to power equal to degree of field characteristic, inversion, and rising to arbitrary power in reduced bases have been described.
References
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.
Published
2018-12-03
Issue
Section
Informatics, computer engineering and control (05.13.00)
