Some Modular Adders and Multipliers for Field Programmable Gate Arrays

This paper is devoted to the study of number representations and algorithms leading to efficient implementations of modular adders and multipliers on recent Field Programmable Arrays. Our hardware operators take advantage of the building blocks available in such devices: carry-propagate adders, memory blocks, and sometimes embedded multipliers. The first part of the paper describes three basic methodologies to carry out a modulo m addition and presents in more details the design of modulo (2^n\pm 1) adders. The major result is a new modulo (2n+1) addition algorithm leading to an area-time efficient implementation of this arithmetic operation on FPGAs. The second part describes a modulo m multiplication algorithm involving small multipliers and memory blocks, and modulo (2n+1) multipliers based on Ma's algorithm. We also suggest some improvements of this operator in order to perform a multiplication in the group (\mathbb{Z}^*_{2^n+1}, \cdot)Cet article est consacré à l'étude de systèmes de représentation des nombres et algorithmes conduisant à des implantations efficaces d’additionneurs et de multiplieurs modulo m sur les FPGA actuels. Nos opérateurs matériels tirent parti des briques de base disponibles dans de tels circuits : additionneurs à retenue propagée, blocs de mémoire et petits multiplieurs. La première partie de l’article décrit trois méthodes de conception d’additionneurs modulo m et présent plus particulièrement et additionneurs modulo (2n+1). Le principal résultat est un nouvel additionneur modulo ( 2n + 1) conduisant à un opérateur compact et rapide sur FPGA. La seconde partie propose un algorithme de multiplication modulo m requérant des petits multiplieurs et des blocs de mémoire. Nous présentons également un multiplieur modulo (2N + 1) basé sur l'algorithme de Ma et suggérions quelques modifications afin d 'effectuer la multiplication dans le groupe (Z*2n +1