Cryptology ePrint Archive: Report 2014/561

Performance Increasing Approaches For Binary Field Inversion

Vladislav Kovtun and Maria Bulakh

Abstract: Authors propose several approaches for increasing performance of multiplicative inversion algorithm in binary fields based on Extended Euclidean Algorithm (EEA). First approach is based on Extended Euclidean Algorithm specificity: either invariant polynomial u remains intact or swaps with invariant polynomial v. It makes it possible to avoid necessity of polynomial v degree computing. The second approach is based on searching the "next matching index" when calculating the degree of the polynomial, since degree polynomial invariant u at least decreases by 1, then it is possible to use current value while further calculation the degree of the polynomial.

Category / Keywords: implementation / binary field, multiplicative inversion, Extended Euclidean Algorithm

Date: received 18 Jul 2014, last revised 18 Jul 2014

Contact author: vladislav kovtun at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140718:210112 (All versions of this report)

Short URL: ia.cr/2014/561

Discussion forum: Show discussion | Start new discussion