Skip to main content
placeholder image

Improving euclidean division and modular reduction for some classes of divisors

Conference Paper


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.

Publication Date


  • 2003

Citation


  • Bajard, J. C., Imbert, L., & Plantard, T. (2003). Improving euclidean division and modular reduction for some classes of divisors. In Conference Record of the Asilomar Conference on Signals, Systems and Computers Vol. 2 (pp. 2218-2221).

Scopus Eid


  • 2-s2.0-4143078362

Start Page


  • 2218

End Page


  • 2221

Volume


  • 2

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.

Publication Date


  • 2003

Citation


  • Bajard, J. C., Imbert, L., & Plantard, T. (2003). Improving euclidean division and modular reduction for some classes of divisors. In Conference Record of the Asilomar Conference on Signals, Systems and Computers Vol. 2 (pp. 2218-2221).

Scopus Eid


  • 2-s2.0-4143078362

Start Page


  • 2218

End Page


  • 2221

Volume


  • 2