Methods for Determining a Gaussian Integer Congruent to a Given Gaussian Integer Modulo a Gaussian Integer Modulus and for Determining a Reduction of a Given Gaussian Integer Modulo a Gaussian Integer Modulus

A method for generating cryptographic key and/or for encryption decryption, the method comprising:

• determining a Gaussian integer congruent to a given Gaussian integer modulo a Gaussian integer modulus, wherein the norm of the Gaussian integer is smaller than the norm of the square of the Gaussian integer modulus by:
• considering a real integer base raised to a first integer exponent having a norm larger than that of the real and larger than that of the imaginary part of the Gaussian integer modulus, wherein a second integer exponent is considered that is equal to or smaller than −2 and wherein a third integer exponent is considered, that is equal to or larger than the first integer exponent incremented by one;
• considering a variable value candidate for the Gaussian integer congruent is considered that is
• first initialized with the given Gaussian integer;
• and
• decrementing the Gaussian integer, either fully or in truncated form, by a multiple of the Gaussian integer modulus;
• evaluating the multiple of the Gaussian integer modulus by calculating an auxiliary product of a component-wisely down rounded quotient of the current value of the variable value candidate for the Gaussian integer congruent and the real integer base raised to the sum of the first integer exponent and the second integer exponent with a prefactor and
• calculating a component-wisely down rounded quotient of this auxiliary product and the real integer base raised to the difference of the third integer exponent and the second integer exponent and multiplying this latter quotient with the Gaussian integer modulus.