Montgomery multiplication over rings

    Authors

    J. P. Brennan;R. Katti

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abstract

    Montogomery 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)(x). 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. (C) 2008 The Franklin Institute. Published by Elsevier Ltd. All rights reserved.

    Journal Title

    Journal of the Franklin Institute-Engineering and Applied Mathematics

    Volume

    346

    Issue/Number

    1

    Publication Date

    1-1-2009

    Document Type

    Article

    First Page

    10

    Last Page

    16

    WOS Identifier

    WOS:000262611600002

    ISSN

    0016-0032

    Share

    COinS