Systolic design space exploration of polynomial division over GF(m2)

Field polynomial division can be found in applications such as error detection and data encoding for digital communication systems. In addition, it implements the extended Euclidean algorithm (EEA), which can be used as the field inversion building block of elliptic curve cryptosystem. The unpredictability of the iterative algorithm of polynomial division in the EEA-Based field inversion results in complex control function and higher CPD. Therefore, many attempts have been made to realize this process in systolic array architectures to be suitable for VLSI implementations. In this paper, binary polynomial division is revisited and the algorithm is analyzed to systematize its process. As a result, an iterative equation that is suitable for systolic array architectures is driven. Then, a systematic methodology for designing systolic arrays for such an algorithm is presented and utilized. Finally, the obtained architectures are discussed and compared with different proposed implementations in the literature.