Fast FPGA Implementations of Inversions for Special Irreducible Polynomials in Finite Field
Haibo Yi, Weijian Li, Zhe Nie · Advanced science and technology letters · 2016
Inversions in finite field have been playing a key role in areas of cryptography and engineering. The main algorithms for finite field inversions are based on Fermat's little theorem, extended Euclidean algorithm and other methods. We present techniques to exploit special irreducible polynomials for fast inversions in finite fields (2 ) n GF , where n is a positive integer. We propose fast inversions based on Fermat's theorem for two special irreducible polynomials, i.e. trinomials and All-One-Polynomials (AOPs). Trinomials can be represented by polynomials 1 n m x x and AOPs can be represented by polynomials 1 ... 1 n n x x , where m is a positive integer and 0<m<n. Our designs are programmed in Very-High-Speed Integrated Circuit Hardware Description Language (VHDL) by using Quartus II and implemented on a lowcost Field-Programmable Gate Array (FPGA). The experimental results show that our designs provide significant reductions in executing time.