Protection of Sensitive Messages Based on Quadratic Roots of Gaussians: Groups with Complex Modulus*

This paper considers three algorithms for the extraction of square roots of complex integers {called Gaus-sians} using arithmetic based on complex modulus p + iq. These algorithms are almost twice as fast as the analogous algorithms extracting square roots of either real or complex integers in arithmetic based on modulus p, where p is a real prime. A cryptographic system based on these algorithms is provided in this paper. A procedure reducing the computational complexity is described as well. Main results are explained in several numeric illustrations