[Resource Topic] 2005/078: Duality between Multiplication and Modular Reduction

Welcome to the resource topic for 2005/078

Duality between Multiplication and Modular Reduction

Authors: Wieland Fischer, Jean-Pierre Seifert


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.

ePrint: https://eprint.iacr.org/2005/078

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .