Volltext-Downloads (blau) und Frontdoor-Views (grau)

Montgomery Reduction for Gaussian Integers

  • Modular arithmetic over integers is required for many cryptography systems. Montgomeryreduction is an efficient algorithm for the modulo reduction after a multiplication. Typically, Mont-gomery reduction is used for rings of ordinary integers. In contrast, we investigate the modularreduction over rings of Gaussian integers. Gaussian integers are complex numbers where the real andimaginary parts are integers. Rings over Gaussian integers are isomorphic to ordinary integer rings.In this work, we show that Montgomery reduction can be applied to Gaussian integer rings. Twoalgorithms for the precision reduction are presented. We demonstrate that the proposed Montgomeryreduction enables an efficient Gaussian integer arithmetic that is suitable for elliptic curve cryptogra-phy. In particular, we consider the elliptic curve point multiplication according to the randomizedinitial point method which is protected against side-channel attacks. The implementation of thisprotected point multiplication is significantly faster than comparable algorithms over ordinary primefields.

Export metadata

Additional Services

Share in Twitter Search Google Scholar


Author:Malek Safieh, Jürgen FreudenbergerORCiDGND
Parent Title (English):Cryptography
Place of publication:Basel
Document Type:Article
Year of Publication:2021
Release Date:2021/04/19
Tag:Elliptic curve point multiplication; Gaussian integers; Mont-gomery modular reduction; Public-key cryptography
Page Number:18
Open Access?:Ja
Relevance:Peer reviewed Publikation in Master Journal List
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International