New algorithm and fast VLSI implementation for modular inversion in Galois field GF(p)

Modular inversion is one of the kernel arithmetic operations in public key cryptosystems, so the design of low-cost and high-speed hardware implementation is absolutely necessary. In this paper, an improved algorithm for prime fields is presented for hardware facilitation and optimization. The hardware-oriented algorithm involves only ordinary addition/subtraction, and does not need any modular operations or multiplication and division. All of the arithmetic operations in the algorithm can be accomplished by only one adder. These features make it very suitable for fast small VLSI implementation. The VLSI implementation of the algorithm is also given and shows the high performance and low silicon penalty.