Welcome to the resource topic for 2015/785
Title:
Double-Speed Barrett Moduli
Authors: Rémi Géraud, Diana Maimut, David Naccache
Abstract:Modular multiplication and modular reduction are the atomic constituents of most public-key cryptosystems. Amongst the numerous algorithms for performing these operations, a particularly elegant method was proposed by Barrett. This method builds the operation a \bmod b from bit shifts, multiplications and additions in \mathbb{Z}. This allows building modular reduction at very marginal code or silicon costs by leveraging existing hardware or software multipliers. This paper presents a method allowing doubling the speed of Barrett’s algorithm by using specific composite moduli. This is particularly useful for lightweight devices where such an optimization can make a difference in terms of power consumption, cost and processing time. The generation of composite moduli with a predetermined portion is a well-known technique and the use of such moduli is considered, in statu scientae, as safe as using randomly generated composite moduli.
ePrint: https://eprint.iacr.org/2015/785
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 .