A Family of Modulo $(2^n+1)$ Multipliers

(eng) In this paper, we first describe a novel modulo $(2^n+1)$ addition algorithm suited to FPGA and ASIC implementations, and discuss several architectures of multioperand modulo $(2^n+1)$ adders. Then, we propose three implementations of a modulo $(2^n+1)$ multiplication algorithm based on a paper by A. Wrzyszcz and D. Milford. The first operator is based on an $n\times n$ multiplication and a subsequent modulo $(2^n+1)$ correction, and takes advantage of the arithmetic logic embedded in Spartan or Virtex FPGAs. The second operator computes a sum of modulo-reduced partial products by means of a multioperand modulo $(2^n+1)$ adder. Then, radix-$4$ modified Booth recoding reduces the number of partial products, while making their generation more complex. Finally, we provide a comparison of this family of algorithms with existing solutions