Paper 2005/078

Duality between Multiplication and Modular Reduction

Wieland Fischer and Jean-Pierre Seifert

Abstract

This paper presents a duality between the classical optimally speeded up multiplication algorithm and some "fast" reduction algorithm. For this, the multiplier is represented by the unique signed digit representation with minimal Hamming weight using Reitwiesner's multiplier recoding algorithm. In fact, the present paper proves that this optimal multiplier recoding technique naturally translates into a canonical modular reduction technique. The other direction is shown as well. Thus, the resulting reduction algorithm is optimal with respect to its average-time complexity as well. Besides these two new results, our proof of the transfer-theorem serves another interesting purpose: The reason that the considered reduction algorithm from \cite{Sedlak} is so unknown might lie in the fact that it is rather un-intuitive and no proper understanding was available so far. Therefore, our proper mathematical derivation/explanation solves this lack of understanding.

Metadata
Available format(s)
PDF PS
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Modular reduction
Contact author(s)
Jean-Pierre Seifert @ intel com
History
2005-03-16: received
Short URL
https://ia.cr/2005/078
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/078,
      author = {Wieland Fischer and Jean-Pierre Seifert},
      title = {Duality between Multiplication and Modular Reduction},
      howpublished = {Cryptology {ePrint} Archive, Paper 2005/078},
      year = {2005},
      url = {https://eprint.iacr.org/2005/078}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.