New multipliers modulo 2N-1

Techniques for computing the product of two N-bit integers modulo 2^N-1 from their k-bit byte decompositions are presented. A modulus 2^N-1 is chosen, as multiplication performed in this modulus can be reconstructed from the cyclic convolution between the sequences of the k-bit bytes of the decomposed numbers. It is shown that cyclic convolutions can be computed using only additions and squaring operations but not two-operand multiplications. Since the squaring operation is a one-operand operation, significant savings in ROM bits can be obtained if look-up tables are used