Title :
O(log2 m) iterative algorithm for multiplicative inversion in GF(2m)
Author :
Morioka, Sumio ; Katayama, Yasunao
Author_Institution :
Tokyo Res. Lab., IBM Res., Kanagawa, Japan
Abstract :
A new algorithm that can calculate the multiplicative inverses in GF(2m) with O(log2 m) iterations is presented. While this algorithm requires in total the same number of multiplications ([log2(m-1)]+Hw(m-1)-1) with the best known algorithm, the latency, if mapped to a hardware, can be reduced significantly ([log2(m-2)]+1), comparable to the best case result, which is implemented using Fermat´s little theorem
Keywords :
Galois fields; information theory; iterative methods; sequences; Fermat´s little theorem; GF(2m); O(log2 m) iterations; iterative algorithm; latency; multiplicative inversion; Elliptic curve cryptography; Iterative algorithms;
Conference_Titel :
Information Theory, 2000. Proceedings. IEEE International Symposium on
Conference_Location :
Sorrento
Print_ISBN :
0-7803-5857-0
DOI :
10.1109/ISIT.2000.866747