Montgomery multiplication over rings

Montgomery multiplication of two elements a and b of a finite field F q is defined as abr - 1 where r is a fixed field element in F q × . In this paper we define Montgomery multiplication of elements a ( x ) and b ( x ) in a polynomial ring modulo the ideal generated by a reducible polynomial f ( x ) . We then show that Montgomery multiplication over a field represented by a polynomial ring modulo an irreducible pentanomial can be performed more efficiently in terms of time delay by embedding the field in a quotient of a polynomial ring modulo a reducible trinomial. The trinomial has a degree that is slightly higher than that of the pentanomial, thereby increasing the number of gates in the multiplier by a small amount.