An improvement of the TYT algorithm for GF(2M) based on reusing intermediate computation results
Gongliang Chen, Yi‐Yang Chen, Jianhua Li, Yin Li · Communications in Mathematical Sciences · 2011
Multiplicative inversion plays an important role to Elliptic Curve Cryptosystems.This paper presents an efficient inversion algorithm in GF (2 m ) using a normal basis which improves the Itoh-Tsujii (IT) algorithm and the Takagi et al. (TYT) algorithm .The proposed algorithm reduces the number of required multiplications by decomposing m -1 into several factors plus a remainder and by reusing intermediate computation values.It is proved that the decomposition of m -1 can be made simpler, but requires even fewer multiplications.Furthermore, a practical algorithm for finding an optimal decomposition of m -1 is investigated.