Improving Euclidean Division and Modular Reduction for Some Classes of Divisors

Jean-Claude Bajard 1 Laurent Imbert 1 Thomas Plantard 2
1 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Modular arithmetic is becoming an area of major importance for many modern applications; RNS is widely used in digital signal processing, and most public-key cryptographic algorithms require very fast modular multiplication , and exponentiation. When such an arithmetic is required, specific values such as Fermat or Mersenne numbers are often chosen since they allow for very efficient implementations. However, there are cases where only very few of those numbers are available. We present an algorithm for the Euclidean division with remainder and we give the classes of divisors for which our algorithm is particularly efficient compared to commonly used method.
Document type :
Conference papers
Complete list of metadatas
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00269572
Contributor : Christine Carvalho de Matos <>
Submitted on : Friday, June 7, 2019 - 5:14:33 PM
Last modification on : Monday, June 10, 2019 - 9:08:21 AM

File

ASILOMAR2003.pdf
Files produced by the author(s)

Identifiers

Collections

ARITH | LIRMM | MIPS | UNIV-MONTPELLIER

Citation

Jean-Claude Bajard, Laurent Imbert, Thomas Plantard. Improving Euclidean Division and Modular Reduction for Some Classes of Divisors. Asilomar Conference on Signals, Systems and Computers, Nov 2003, Asilomar, CA, United States. pp.2218-2221, ⟨10.1109/ACSSC.2003.1292374⟩. ⟨lirmm-00269572⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

111

Files downloads

14

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD