A combined multiplication/division algorithm for efficient design of ECC over GF(2^m)

Using the concept of reciprocal polynomial, this paper shows that a field multiplication over GF(2^m) can be implemented by the extended Stein algorithm, one of the algorithms used to realize division. With a fundamental change at the algorithmic level, the field multiplication can be efficiently embedded into a divider so that the multiplier can be eliminated with very little hardware overhead for operand selection. When applied to Elliptic Curve Cryptography (ECC) using affine coordinates, about 13.8% reduction on the area requirement can be achieved with almost no performance degradation compared with the one implemented with two distinct components. Experimental results show that the combined multiplication and division circuit achieves area advantages in comparison with other low-cost designs. The area-efficient design of ECC system also exhibits obvious improvement in area-time (AT) complexity.