An Efficient Barrett Reduction Algorithm for Gaussian Integer Moduli
Malek Safieh, Andreas Furch, Fabrizio De Santis · 2023
Gaussian integers are a subset of complex numbers that have integer numbers in both their real and imaginary parts. Similar to ordinary integer numbers, they can be equipped with modulo operations, which creates Gaussian integer rings and fields. Depending on the chosen modulus, these structures can be isomorphic to corresponding algebraic structures over integer numbers. However, computing modulo reduction for Gaussian integers can be computationally expensive, especially when the modulus itself is a Gaussian integer.In this work, we present a novel and efficient reduction algorithm for Gaussian integer moduli of arbitrary form based on the ideas of Barrett reduction for integer numbers. We show that the computational complexity of our proposed reduction algorithm is equivalent to previously known Montgomery reduction over Gaussian integers. However, unlike Montgomery’s approach, our algorithm does not require domain transformations and can be more advantageous in various circumstances.