Ефективне обчислення квадратного кореня на полях галуа GF(2m)
Анотація
У статті запропоновано спосіб прискореного обчислення кореня на полях Галуа GF (2m). Показано, що
задача обчислення коренів на полях Галуа може бути зведена до розв'язання системи лінійних бітових рів-
нянь. Запропоновано технологію реалізації цієї теоретичної ідеї. Доведено, що обчислювальна складність
O(m) запропонованого способу істотно менша, ніж складність відомих способів, що становить O(m2).
Посилання
Menezes A. Elliptic Curve Public Key Cryptosystems. / Menezes A. - Kluwer Academic Published.-1993 - 422 р.
Tonelli A. Bemerkung über die Auflösung quadratischer Congruenzen / Tonelli A. // Göttinger Nachrichten.-
- PP.344-346.
Boneh D. Identity-based encryption from the Well pairing / Boneh D., Franclin M. // SIAM Journal of
Computing.- Vol.23.- 2003.- № 3.- PP. 354-368.
Barreto P.S.L.M. Efficient Computation of Root in Finite Fields / Barreto P.S.L.M., Voloch J.F. // Designs,
Codes and cryptography.- 2006.- № 39.- pp. 275-280.
Cipolla M. Un metodo per la risolutione della congruenza di secondo grado / Cipolla M. // Rendiconto
dell’Accademia Scienze Fisiche e Matematiche.- Napoli.-1903.- Ser.3- Vol.IX.- PP.154-163.
Aldeman L.M. On taking root in finite fields / Aldeman L.M., Manders K. Miller G. // Proc. 18-th IEEE
Symposium on Foundations of Computer Science.-1977.-PP.175-177.
Марковський О.П. Спосіб прискореного обчислення коренів на полях Галуа GF(2m) / Марковський
О.П., Виноградов Ю.М., Косейкіна Г.С. // Вісник Національного технічного університету України
”KПI” Інформатика, управління та обчислювальна техніка, – Київ: ВЕК+ – 2012 – № 56. с.165-168.
