Quadrinomial modular arithmetic using modified polynomial basis
Christophe Négre · 2005
Finite field arithmetic has advantageous space and time complexity when the field is constructed with a sparse polynomial. Katti and Brennan in (May, 20023) introduced a new type of polynomial, which we will call here the nearly all one polynomial (NAOP), and they show that NAOP modular arithmetic is roughly equivalent to quadrinomial arithmetic. In this paper we will introduce a new representation : the modified polynomial basis, to compute modulo quadrinomials. We obtain a faster bit-parallel multiplier in F/sub 2//sup n/ with time complexity equal to T/sub A/ + (2 + /spl lceil/log/sub 2/(n + 1)/spl rceil/)T/sub X/ and a space complexity equal to (n + 1) /sup 2/ AND and ((n + 1) /sup 2/ + m - k - 1) XOR. For fields F/sub 2//sup n/ of degree n ranging between 160 and 500, which cannot be constructed with an irreducible trinomial or an optimal normal basis, our multiplier improve by 8% the time complexity of the previous multipliers proposed (Mastrovito,1991; Katti and Brennan,2003; Rodriguez-Henriquez and Koc, 2003), in compensation the space complexity is increased by 1.5%.