Fast Montgomery-Like Square Root Computation for All Trinomials

Yin LI  Yu ZHANG  Xiaoli GUO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.1   pp.307-309
Publication Date: 2019/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.307
Type of Manuscript: LETTER
Category: Coding Theory
finite field,  square root,  inversion,  cryptography,  

Full Text: PDF(224.8KB)
>>Buy this Article

We introduce a new type of Montgomery-like square root formulae in GF(2m) defined by an arbitrary irreducible trinomial, which is more efficient compared with classic square root operation. By choosing proper Montgomery factors 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.