Opérateurs itératifs de multiplication-addition modulaire pour FPGA

Jean-Luc Beuchat 1, 2 Jean-Michel Muller 1, 2
1 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : This paper descirbes several improvement of an iterative algorithm for modular multiplication originnaly proposed by Jeong and Burleson. A first modification of the recurrence relation allows us to implement a fused multiply and add unit. Then, we sho how to reduce the circuit area by a factor two when the operator offers the possibility to choose the modulo among a set m_1,m_2,,.m_q; A new iterative algorithm making the implementation of modular exponentiation easier is eventually discussed. For 16-bit numbers, ours operators perform for instance 6 millions of operations per second on a Virtex-E device while only requiring 17 slices.These operators involve small tables depending on the required set of moduli. A straightforward approach is to automatically generate a VHDL description of the modular multiplier according to m_1, m_2,, m_q. That design methodology assumes that the moduli are known a priori ansd works only for small sets of moduli. In order to avoid these drawbacks, we propose here an algorithm that allows to build the table while we perform the first steps of the modular multiplication
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00071642
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:23:05 PM
Last modification on : Tuesday, May 21, 2019 - 2:18:49 PM

Identifiers

  • HAL Id : inria-00071642, version 1

Collections

Citation

Jean-Luc Beuchat, Jean-Michel Muller. Opérateurs itératifs de multiplication-addition modulaire pour FPGA. [Rapport de recherche] RR-4937, LIP RR-2003-40, INRIA, LIP. 2003. ⟨inria-00071642⟩

Share

Metrics

Record views

263

Files downloads

890