Computer-implemented method for determining a Gaussian inte- ger congruent to a given Gaussian integer modulo a Gaussian integer modulus, method for determining a reduction of a giv- en Gaussian integer modulo a Gaussian integer modulus and cryptographic method and error-correction method

The invention relates to a computer-implemented method for determining a Gaussian integer congruent to a given Gaussian integer modulo a Gaussian integer modulus and to a method for a complete modulo reduction of a given Gaussian integer with a Gaussian integer modulus. The invention furthermore relates to a computer-implemented cryptographic method and to a com- puter-implemented error-correction method.

Gaussian integers are a subset of the complex numbers having integers as real and imaginary parts. The set of Gaussian in- tegers together with addition and multiplication modulo a Gaussian integer modulus forms either a ring or a field de- pending on the choice of the modulus. For this reason, Gauss- ian integers find applications in error-correcting coding theory, cryptography, and other fields of sciences.

For example, the set of Gaussian integers with addition and multiplication modulo a Gaussian integer modulus n forms a finite Gaussian integer field, if nn*=p is prime and thus an ordinary integer. Note that the notion n*denotes the complex conjugate of n. In this case, the resulting Gaussian integer field is isomorphic to the prime field GF(p) over ordinary integers. Such an isomorphism exists for any prime p congru- ent to 1 modulo 4.

Like for the case of ordinary integers, the straightforward implementation of a modulo reduction of a given Gaussian in- teger is typically quite inefficient, because it requires a division of a Gaussian integer followed by a rounding of the result. Hence, more efficient reduction mechanisms for Gauss- ian integers are needed.

In the fields of cryptography and error-correction codes, congruent solutions with a smaller norm or absolute value than the original given Gaussian integer are heavily used and typically computed relatively inefficient.

The current invention aims at providing a method for an effi- cient reduction of a given Gaussian integer with a Gaussian integer modulus. Likewise, also a method for determining a Gaussian integer congruent to a given Gaussian integer modulo a Gaussian integer modulus with reduced complexity would be beneficial for many applications. Cryptographic methods and error-correction methods would significantly benefit from ef- ficient reduction methods as mentioned above and are highly desired.

The problem of this invention is solved with a computer- implemented method for determining a Gaussian integer congru- ent to a given Gaussian integer modulo a Gaussian integer modulus having the features contained in claim 1, with a method for a reduction of a given Gaussian integer with a Gaussian integer modulus having the features contained in claim 13 and with a computer-implemented cryptographic method having the features contained in claim 14 and with a comput- er-implemented error-correction method having the features contained in claim 15.

Preferred and advantageous aspects of the invention are con- tained in the respective dependent claims and the subsequent description.

The main idea of the current invention is to provide an effi- cient reduction method for Gaussian integer moduli that boils down to a sequence of elementary bit operations, hence providing a very fast way to implement modulo reduction (both when using software and/or hardware) for a large class of Gaussian integer moduli.

A classic and direct approach for a modulo reduction of a given Gaussian integer x modulo a Gaussian integer modulus n uses a subtraction, three complex multiplications and two in- teger divisions in total due to a complex division with rounding, that involves an complex multiplication of both nominator and denominator with the complex-conjugate of the denominator,, like shown in the following formula: x mod n = x - [(xn*)/(nn*)]-n.

Again, the notion n*denotes the complex conjugate of n, and the square brackets denote the operation of rounding.

A more efficient method for performing a modulo reduction of a given Gaussian integer modulo a Gaussian integer modulus is described in the following article: Safieh, Malek; Freuden- berger, Jurgen: "Montgomery Reduction for Gaussian Integers", Cryptography 2021, 5, 6 (https://doi.org/10.3390/cryptography5010006).

Likewise, fast reduction methods for a special class of ordi- nary integers are known. However, efficient reduction methods for Gaussian integers are less developed. Thus, the invention in a particularly advantageous aspect addresses the important use case of given Gaussian integers, which are not ordinary integers.

According to this invention, the modulo reduction may be per- formed in two parts: in a first part, a Gaussian integer con- gruent replacing the given Gaussian integer is determined, which is smaller than the given Gaussian integer, with re- spect to a norm such as the absolute value, but congruent to a final reduced result. In a second part, the congruent re- sult may be reduced to obtain the final result of the modulo reduction, which is the correct representative from the Gaussian integer ring or field. Both aspects, the determina- tion of the Gaussian integer congruent and the complete re- duction, are subject of the current invention.

In this invention an efficient algorithm for the modulo re- duction of given Gaussian integers in two parts as described above is disclosed. The first part is new and leads to dif- ferent algorithmic steps and arithmetic operations than those described in prior art. This first part may be combined with a second part known from Safieh, Malek; Freudenberger, Jur- gen: "Montgomery Reduction for Gaussian Integers", Cryptog- raphy 2021, 5, 6 (https://doi.org/10.3390/cryptography5010006) as steps 3 to 11 of Algorithm 2 which constitute prior art.

Both the first and the second part may be combined to perform a full modulo reduction. However, in practice the first part is performed more frequently, particularly during crypto- graphic computations, while the second part, that may be also referred to as the "final reduction" throughout this applica- tion, is performed only once at the end to obtain the final desired result, the so-called representative of the Gaussian integer ring or field, which is the result from a modulo re- duction. Moreover, the second part is based on computational- ly intensive comparisons. Thus, the first part aims at reduc- ing the number of these comparisons to decrease the total complexity.

Thus, particularly the novel part of determining a Gaussian integer congruent to a given Gaussian integer modulo a Gauss- ian integer modulus provides major benefits in the efficiency of modulo reductions of Gaussian integers. Furthermore, it enables a final reduction with reduced complexity, i.e., the final reduction presented as steps 3 to 11 of algorithm 2 in the article: Safieh, Malek; Freudenberger, Jurgen: "Montgom- ery Reduction for Gaussian Integers", Cryptography 2021, 5, 6 (https://doi.org/10.3390/cryptography5010006) . The computer-implemented method according to the invention is a method for determining a Gaussian integer congruent to a given Gaussian integer modulo a Gaussian integer modulus. In the method according to the invention, the norm of the Gauss- ian integer is smaller than the norm of the square of the Gaussian integer modulus. In the method according to the in- vention, a real integer base raised to a first integer expo- nent is considered, that has a norm that is larger than the norm of the real part of the Gaussian integer modulus and that is also larger than the norm of the imaginary part of the Gaussian integer modulus. Furthermore, a second integer exponent is considered that is equal to or smaller than -2 and, additionally, a third integer exponent is considered, that is equal to or larger than the first integer exponent incremented by one. A variable value candidate for the Gauss- ian integer congruent is considered in the method according to the invention that is first initialized with the given Gaussian integer, wherein the Gaussian integer is, either fully or in truncated form, decremented by a multiple of the Gaussian integer modulus, the multiple of the Gaussian inte- ger modulus being evaluated by calculating an auxiliary prod- uct of a component-wisely down rounded quotient of the cur- rent 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 by calculating a component-wisely down rounded quotient of this auxiliary product and the real inte- ger base raised to the difference of the third integer expo- nent and the second integer exponent and multiplying this last mentioned quotient with the Gaussian integer modulus.

This means, the variable value candidate for the Gaussian in- teger congruent, that has been initialized with the Gaussian integer, is decremented by a multiple of the Gaussian integer modulus as described above.

"The first integer exponent incremented by one" may prefera- bly also be expressed as "the first integer exponent plus one" or as "the first integer exponent incremented by unity". In other words, "The first integer exponent incremented by one" means the result of adding the number 1 to the first in- teger exponent.

Hereafter, the resulting variable value candidate for the Gaussian integer congruent determines the Gaussian integer congruent with reduced norm or absolute value, which directly enables the use of the final reduction presented as steps 3 to 11 of algorithm 2 in the article: Safieh, Malek; Freuden- berger, Jurgen: "Montgomery Reduction for Gaussian Integers", Cryptography 2021, 5, 6 (https://doi.org/10.3390/cryptography5010006).

In this context, the wording "Gaussian integer congruent" de- notes a Gaussian integer which is congruent to a given Gauss- ian integer modulo a Gaussian integer modulus. The invention may also be directed to the goal of determining such a Gauss- ian integer congruent, that has a norm that is smaller than the norm of the given Gaussian integer. Determining such a Gaussian integer congruent directly enables the use of the final reduction presented as steps 3 to 11 of algorithm 2 in the article: Safieh, Malek; Freudenberger, Jurgen: "Montgom- ery Reduction for Gaussian Integers", Cryptography 2021, 5, 6 (https://doi.org/10.3390/cryptography5010006).

Thus, in a particular aspect of the invention, the Gaussian integer congruent determined with the method according to the invention has a norm that is smaller than the norm of the given Gaussian integer.

Throughout this application, the terms mentioned below have the following meaning:

The term Gaussian integer modulus denotes a complex modulus, that has an arbitrary form. However, in an advantageous and preferred aspect of the invention, the invention is applied to such a Gaussian integer modulus that is not an ordinary integer. Later on, particularly in the description of pre- ferred embodiments, the Gaussian integer modulus may also be denoted as n.

Throughout this application, the term given Gaussian integer refers to Gaussian integers, thus including ordinary inte- gers. The given Gaussian integer may be denoted as z' and may initialize the variable value candidate in what follows, par- ticularly in the description of preferred embodiments.

Throughout this application, the term real integer base raised to an integer exponent refers to a base, that is a re- al integer and that is raised to an exponent, which is an in- teger. Later on, particularly in the description of preferred embodiments, the real integer base is denoted as and the integer exponent may be denoted by any symbol as apparent from the respective context.

Throughout this application, the term variable value candi- date for the congruent denotes a candidate for the congruent, that can take temporary and changing Gaussian integer values during the determination according to the method according to the invention. However, the variable value candidate is - af- ter decrementing - in a preferred aspect of the invention congruent to the given Gaussian integer modulo the Gaussian integer modulus. Later, the variable value candidate for the congruent may be denoted by z', particularly in the descrip- tion of preferred embodiments.

It is understood, that the phrase "variable value candidate that is decremented by" a quantity means that this quantity is subtracted from the variable value candidate.

The method according to the invention allows a more efficient determination of a Gaussian integer congruent to a given Gaussian integer modulo a Gaussian integer modulus. Advanta- geously, the method according to the invention involves the computation of quotients that can be performed using computa- tionally efficient digit shifts.

In an advantageous and optional aspect of the method accord- ing to the invention, such a second integer exponent is con- sidered that is equal to or smaller than -3 and such a third integer exponent is considered, that is equal to or larger than the first integer exponent incremented by three.

Preferably, in the method according to the invention, the Gaussian integer is decremented by a multiple of the Gaussian integer modulus in a truncated form such that the Gaussian integer is truncated via modulo reduction of the Gaussian in- teger modulo the real integer base raised to the difference of the third integer exponent and the second integer exponent and the multiple of the Gaussian integer modulus is truncated via modulo reduction of the multiple of the Gaussian integer modulus modulo the real integer base raised to the difference of the third integer exponent and the second integer exponent and subtracted from the truncated Gaussian integer. After subtracting the truncated multiple of the Gaussian integer modulus, the result is considered the decremented Gaussian integer.

Alternatively and also advantageously, the truncation may be performed after decrementing the Gaussian integer.

In a preferred aspect of the method according to the inven- tion, the prefactor is the down-rounded quotient of the real integer base raised to the sum of the first integer exponent and the third integer exponent and the Gaussian integer modu- lus. Advantageously, this prefactor can be precomputed. Pref- erably, in the method according to the invention, the prefac- tor is precomputed.

In a preferred and advantageous aspect of the invention, the norm denotes the absolute value. Hence, in this aspect of the invention, the norm of the variable value candidate means the absolute value of the variable value candidate and the norm of the given Gaussian integer means the absolute value of the given Gaussian integer. In alternative advantageous aspects of the invention, other norms may be used, particularly the Manhattan weight or the absolute square value of the variable value candidate.

In a preferred aspect of the method according to the inven- tion, the method is conducted on a computer that stores num- bers in a positional numeral system with a radix, the radix being equal to the real integer base that, in this aspect of the invention, constitutes an ordinary integer base or the real integer base is the radix raised to an integer number. In this aspect of the invention, the radix of the positional numeral system directly matches the real integer base or the radix of the positional numeral system raised to the integer number matches the real integer base. Hence, many operations in this algorithm may be conducted with positional shifts of digits in the positional numeral system. In this particularly useful aspect of the invention, the computational benefits which the invention provides are directly used and appropri- ated when conducting the method.

In a particular beneficial aspect of the method according to the invention the real integer base is an ordinary integer, particularly 2 or 2 raised to an integer power.

Thus, the method is directly applicable in computers that store numbers as binary numbers. Since this positional numer- al system is widely used in the computational domain, partic- ularly this aspect of the invention addresses almost all com- putational architectures currently available.

In an advantageous and preferred aspect of the invention, in the method the Gaussian integer is reduced using a final re- duction. In a preferred aspect of the invention, the component-wisely down rounded quotient involves operations that may be per- formed particularly efficient with a shift of digits to the right direction. For the real integer base being 2 or 2 raised to an integer number, and a binary numeral system, this operation may be performed with low computational costs by applying conventional bit shifts to the right by a number of digits, particularly by a number of digits that preferably equals to the logarithm of the denominator of the respective quotient to the base 2 or - for other than binary numeral systems - to the base that equals the radix of the numeral system.

The component-wise down rounding of the quotient may be easi- ly achieved by applying digit shifts to the right direction, respectively.

In the computer-implemented method for a reduction of a given Gaussian integer with a Gaussian integer modulus, at first a Gaussian integer congruent to a modulo reduction of a given Gaussian integer with the Gaussian integer modulus is deter- mined with the method as described above and subsequently, the Gaussian integer congruent is further reduced with a fi- nal reduction. A part of the Montgomery reduction, namely the final part given by the steps 3 to 11 of algorithm 2 in the article: Safieh, Malek; Freudenberger, Jurgen: "Montgomery Reduction for Gaussian Integers", Cryptography 2021, 5, 6 (https://doi.org/10.3390/cryptography5010006), constitutes a known reduction which - in combination with the method for determining a Gaussian integer congruent to a modulo reduc- tion of a given Gaussian integer modulo a complex modulus - results in a computationally efficient reduction of Gaussian integers.

The computer-implemented cryptographic method according to the invention is particularly a method for generating a cryp- tographic key and/or for encryption or decryption. In the method according to the invention the cryptographic method involves determining a Gaussian integer congruent to a given Gaussian integer modulo a Gaussian integer modulus and/or de- termining a reduction of a given Gaussian integer modulo a Gaussian integer modulus and the Gaussian integer congruent to the given Gaussian integer modulo the Gaussian integer modulus is determined using a method as described above and/or the reduction of the given Gaussian integer modulo the Gaussian integer modulus is determined using a method as de- scribed above.

In the computer-implemented error-correction method according to the invention, the error-correction method involves deter- mining a Gaussian integer congruent to a given Gaussian inte- ger modulo a Gaussian integer modulus and/or a reduction of a given Gaussian integer modulo a Gaussian integer modulus and the Gaussian integer congruent to the given Gaussian integer modulo the Gaussian integer modulus is determined using a method as described above and/or the reduction of the given Gaussian integer modulo the Gaussian integer modulus is eval- uated using a method as described above.

In the following, embodiments of the invention are described in more detail for a processor that operates with a binary numeral system:

The reduction algorithm is described below as algorithm 1 and contains in steps 1 to 4 the method for determining a congru- ent to a modulo reduction of a given Gaussian integer with a Gaussian integer modulus according to the invention. This method represents the first part of algorithm 1. The second part of algorithm 1 is constituted by a final reduction to determine the correct representative from the Gaussian inte- ger ring or field as used in the Montgomery method. Part 1 and part 2 together form the method for a desired reduction of a given Gaussian integer with a Gaussian integer modulus according to the invention. The full reduction algorithm according to algorithm 1 targets Gaussian integer moduli of the form it= a + bi and I l For efficient processing, a quantity is introduced, that can be precomputed and stored. The real integer base /? in this example is equal to 2 or equal to 2 raised to an integer number:

In the first part in step 1 to 4, a Gaussian integer z' is determined, which is congruent to the correct result of the complete or desired ordinary modulo reduction. Since in the present example, the real integer base in algorithm 1 is equal to 2 or to a power of 2, the evaluation of step 1 and 3 only requires bit shifts into the right direction for the re- al and the imaginary part. The second part in steps 5 to 13, also called the final reduction throughout this application, uniquely determines the correct final result, which is the correct representative from the Gaussian integer field or ring, using the final reduction for Gaussian integers as de- scribed in steps 3 to 11 of algorithm 2 in Safieh, Malek; Freudenberger, Jurgen: "Montgomery Reduction for Gaussian In- tegers", Cryptography 2021, 5, 6 as referenced in the previ- ous description, the content of which is hereby included by reference.

Several cases, the algorithm 1 may be applied to, are distin- guished in the following:

In this example and typically, the real integer base is an ordinary integer base, here e. g. the ordinary integer /3 = 2 or 2 raised to an integer power. In the particular example described here, the real integer base is 2 raised to such an integer power, that the exponentiation results in the word size of the used processor, e. g. 64 for a 64-bit processor. Due to the choice of the integer base /3, steps 1 and 3 in al- gorithm 1, respectively, involve simply bit shifts to the right direction and a truncation. Furthermore, the evaluation of the difference of the Gaussian integer z' and the multiple of the Gaussian integer modulus involves a complex multipli- cation which may not induce much computational costs.

In algorithm 1, the absolute value of the Gaussian integer is smaller than the absolute value of the square of the Gaussian integer modulus. In other words, the Gaussian integer is smaller in absolute value than the square of the Gaussian in- teger modulus.

A first integer exponent, in algorithm 1 also denoted as k, is chosen such, that the real integer base raised to the first integer exponent k, /3 ^k , has a norm, that is larger than the norm of the real part of the Gaussian integer modulus: - The real integer base /3 raised to the first integer exponent additionally has a norm that is larger than the norm of the imaginary part of the Gaussian integer modulus |b|< in Furthermore, for the evaluation of steps 1 to 4, a second in- teger exponent 5 is considered that is equal to or smaller than -2. A third integer exponent y is considered, that is equal to or larger than the first integer exponent raised by one. A variable value candidate for the Gaussian integer con- gruent is considered that is first initialized with the given Gaussian integer z’. In algorithm 1, the variable value can- didate for the Gaussian integer congruent is decremented by a multiple q ₃ 7V of the Gaussian integer modulus 7r in step 4, z’ = z'—q ₃ 7L. For this step 4, the multiple q ₃ 7T of the Gaussian integer modulus is evaluated by calculating an auxiliary product (z' div p^ ³ )/u in step 2 of a component-wisely down rounded quotient z’ div P ⁷ ^ ³ of the current value of the vari- able value candidate z’ for the Gaussian integer congruent and the real integer base raised to the sum k+5 of the first integer exponent k and the second integer exponent 5, P^ ³ , obtained in step 1 with a prefactor, //, and by calculat- ing, in step 3, a down rounded quotient of this auxiliary product Q2 = (z' div P ⁷⁷³ )/u and the real integer base raised to the difference of the third inter exponent and the second integer exponent q3 = q ₃ div p^ ³ and by multiplying this last down rounded quotient q ₃ with the integer modulus 7T. The prefactor /j.= P ⁷⁷⁷ div 7rmay be precomputed and stored.

In other examples, other norms may be used instead of the ab- solute value, such as the Manhattan weight or the absolute square value.

A further embodiment of the method according to the invention deviates from the embodiments described above in those as- pects explicitly mentioned hereafter and corresponds to the previous embodiments in all other aspects.

In this further embodiment, the variable value candidate for the Gaussian integer congruent is decremented by a multiple q ₃ 7T of the Gaussian integer modulus 7T in step 4 not in its full form involving all digits, but the decrementing is car- ried out on a truncated version of the Gaussian integer with a truncated version of the multiple qs7T of the Gaussian inte- ger modulus 7T in step 4. In other words, the relation z' = z'To.odfl'-d-qsTT mod [y ⁵ applies for step 4 instead of the previ- ous step 4 z’ = z’-q:i7T of previous embodiments. Furthermore, for the evaluation of steps 1 to 4, the second integer expo- nent 5 is not only equal to or smaller than -2, but the sec- ond integer exponent 5 satisfies the even stronger condition of being equal to or smaller than -3, i. e. 5 < -3. The third integer exponent y also satisfies an even stronger condition than in the previous embodiments in that it is equal to or larger than the first integer exponent incremented by three, i. e. y > k+3.