Fast VLSI Implementation of Modular Inversion in Galois Field GF（p）

Modular inversion is one of the key arithmetic operations in public key cryptosystems, so low-cost, high-speed hardware implementation is absolutely necessary. This paper presents an algorithm for prime fields for hardware implementation. The algorithm involves only ordinary addition/subtraction and does not need any modular operations, multiplications or divisions. All of the arithmetic operations in the algorithm can be accomplished by only one adder, so it is very suitable for fast very large scale integration (VLSI) implementation. The VLSI implementation of the algorithm is also given with good performance and low silicon penalty.