earticle

영어

Inversions in small finite fields are the most computationally intensive field arithmetic and have been playing a key role in areas of cryptography and engineering. The main algorithms for small finite field inversions are based on Fermat's little theorem, extended Euclidean algorithm, Itoh-Tsujii algorithm and other methods. In this brief, we present techniques to exploit special irreducible polynomials for fast inversions in small finite fields GF(2n) , where n is a positive integer and 0 < n < 16 . Then, we propose fast inversions based on Fermat's theorem for two special irreducible polynomials in small finite fields, i.e. trinomials and All-One-Polynomials (AOPs). Trinomials can be represented by polynomials xn + xm + 1 and AOPs can be represented by polynomials xn + Xn-1 + ... +1 , where m is a positive integer and 0 < m < n . Our designs have low hardware requirements, regular structures and are therefore suitable for hardware implementation. After that, our designs are programmed in Very-High-Speed Integrated Circuit Hardware Description Language (VHDL) by using integrated environment Altera Quartus II and implemented on a low-cost Field- Programmable Gate Array (FPGA). The experimental results on FPGAs show that our designs provide significant reductions in executing time of inversions in small finite fields, e.g. the executing time of inversion in GF(27) is 18.80 ns and the executing time of inversion in GF(212) is 29.57 ns.