ELECTROTECHNIC AND COMPUTER SYSTEMS, Odessa national polytechnic university

MULTIPLIERS FOR GALOIS FIELDS TIME COMPLEXITY

Abstract:

Multipliers for binary Galois field GF (2ⁿ) hardware complexity allows to implement in FPGA an operational device with multiple multipliers. But because of the large structural complexity for some combinations of large order n of field and the multipliers number to make it is practically impossible. One of the possible choices of this problem solving is the move to using Galois fields with the base d, greater than 2. Multipliers for such extended Galois field GF (d^m) with approximately the same number of elements d^m » 2ⁿ are estimated in the article in terms of their time complexity to determine the fields in which the multiplier will have the least time complexity.

Authors:

Elias Rodrigue M. PhD ( rodrigue.elias@liu.edu.lb, ORCID ID: 0000-0003-4506-0368 )
Hlukhov Valerij S. Dr. of Science, Professor ( glukhov@polynet.lviv.ua, ORCID ID:0000-0002-0542-7447 )
Rahma Mokhammed K. ( muhamed_kadhem@yahoo.com, ORCID ID: 0000-0002-8377-1833 )

Keywords

time complexity - Galois field - expanded field - base of the field - order of the field – multiplier

DOI

http://dx.doi.org/10.15276/eltecs.22.98.2016.55

References

DSTU 4145-2002. Informatsiyni tekhnolohiyi. Kryptohrafichnyy zakhyst informatsiyi. Tsyfrovyy pidpys, shcho gruntuyet'sya na eliptychnykh kryvykh. Formuvannya ta pereviryannya [Information Technology. Cryptographic Techniques. Digital Signatures Based on Elliptic Curves. Generation and Verification]. Derzhavnyy komitet Ukrayiny z pytan' tekhnichnoho rehulyuvannya ta spozhyvchoyi polityky, Kiyv, Ukraine, 2003 (In Ukrainian).
H.H. Guild. Fully iterative fast array for binary multiplication and addition. Electronics Letters, Volume 5, Issue 12, 12 June 1969, page 263 (In English).
V.S. Hlukhov, R.M.Elias, A.O.Mel'nyk. Osoblyvosti realizatsiyi na PLIS sektsiynykh pomnozhuvachiv elementiv poliv Halua GF(2m) z nadvelykym stepenem [Features of the FPGA-based Galois Field GF(2^m) Elements Sectional Multipliers with Extra Large Exponent]. Komp"yuterno-intehrovani tekhnolohiyi:osvita, nauka, vyrobnytstvo - naukovyy zhurnal, Luts'kyy natsional'nyy tekhnichnyy universytet. Luts'k, Ukraine, 2013, vol. 12, pp. 103 – 106 (In Ukrainian).
Hlukhov V. S., Hlukhova O. V. Rezul'taty otsinky strukturnoyi skladnosti pomnozhuvachiv elementiv poliv Halua [Structural Complexity of Galois Field Elements Multipliers Evaluation Results]. Visnyk Natsional'noho universytetu “L'vivs'ka politekhnika” “Komp"yuterni systemy ta merezhi”. Lviv, Ukraine, 2013, vol. 773, pp. 27-32 (In Ukrainian).
Hlukhov V. S., Trishch H. M. Otsinka strukturnoyi skladnosti bahatosektsiynykh pomnozhuvachiv elementiv poliv Halua [Evaluation of structural complexity multisection multiplier for Galois field elements].Visnyk Natsional'noho universytetu “L'vivs'ka politekhnika” “Komp"yuterni systemy ta merezhi”. Lviv, Ukraine, 2014, vol. 806, pp. 27-33 (In Ukrainian).
Sholohon O. Z. Obchyslennya strukturnoyi skladnosti pomnozhuvachiv u polinomial'nomu bazysi elementiv poliv Halua GF(2^m) [Structural Complexity of Galois Field GF(2^m) Elements Multipliers in Polynomial Basis Calculation]. Visnyk Natsional'noho universytetu “L'vivs'ka politekhnika” “Komp"yuterni systemy ta merezhi”. Lviv, Ukraine, 2014, vol. 806, pp. 284-289 (In Ukrainian).
Sholohon Yu. Z. Otsinyuvannya strukturnoyi skladnosti pomnozhuvachiv poliv Halua na osnovi elementarnykh peretvoryuvachiv [Based on Elementary Transducers Structural Complexity of Galois Field Multipliers Evaluation]. Visnyk Natsional'noho universytetu “L'vivs'ka politekhnika” “Komp"yuterni systemy ta merezhi”. Lviv, Ukraine, 2014,vol. 806, pp. 290-295 (In Ukrainian).
Hlukhov V.S., Elias R. Umenshenie strukturnoy slozhnosti mnogosektsionnyih umnozhiteley elementov poley Galua [Galois Fields Elements Multisection Multipliers Structural Complexity Reduction]. Elektrotehnicheskie i kompyuternyie sistemyi. - 2015. - № 19(95) - pp. 222-226 (In Russian).
M. Zholubak, A. T. Kostyk, V. S. Hlukhov. Osoblyvosti opratsyuvannya elementiv triykovykh poliv Halua na suchasniy elementniy bazieskye y komp'yuternыe systemы[Features of processing Binary Galois fields elements on modern hardware base].Visnyk Natsional'noho universytetu “L'vivs'ka politekhnika” “Komp"yuterni systemy ta merezhi”. Lviv, Ukraine, 2015,vol. 830, pp. 27-33 (In Ukrainian).