GF(2n) Montgomery multiplication using Polynomial Residue Arithmetic
Dimitrios Schinianakis, Alexander Skavantzos, Thanos Stouraitis · 2012
A methodology for incorporating Polynomial Residue Arithmetic (PRA) in the Montgomery multiplication algorithm for polynomials in GF(2n) is presented in this paper. The mathematical conditions that need to be satisfied, in order for this incorporation to be valid are examined and performance results are given in terms of the field characteristic n, the number of moduli elements L, and the moduli word-length w. The proposed architecture is highly parallelizable and flexible, as it supports Polynomial-to-PRA and PRA-to-Polynomial conversions, Chinese Remainder Theorem (CRT) for polynomials, Montgomery multiplication, and Montgomery exponentiation in the same hardware.