Paper 2017/064

Fast Montgomery-like Square Root Computation for All Trinomials

Yin Li and Yu Zhang

Abstract

We introduce a new type of Montgomery-like square root formulae in $GF(2^m)$ defined by an arbitrary irreducible trinomial, which is more efficient compared with classic square root operation. By choosing proper Montgomery factor for different kind of trinomials, the space and time complexities of such square root computations match or outperform the best results. A practical application of the Montgomery-like square root in inversion computation is also presented.