10.2 Multiplicative Inverse in Residue Class Rings

Team-Fly

10.2 Multiplicative Inverse in Residue Class Rings

In contrast to the arithmetic of whole numbers, in residue class rings it is possible, under certain assumptions, to calculate with multiplicative inverses. Namely, many elements ā Î , not necessarily all, possess a suitable Î such that ā · = . This is equivalent to the assertion that the congruence a · x ≡ 1 mod n and the statement a · x mod n = 1 hold. For example, in , and are multiplicative inverses of each other, since 15 mod 14 = 1.

The existence of multiplicative inverses in is not obvious. In Chapter 5, on page 68, it was determined only that (, ·) is a finite commutative semigroup with unit . A sufficient condition for an element ā Î to possess a multiplicative inverse can be obtained with the help of the Euclidean algorithm: The second-to-last equation in the Euclidean algorithm procedure on page 167,

can be transformed into

(1)

If we continue in this fashion, then we obtain in succession

(2)

(3)

If in (1) we replace a_m−1 by the right side of equation (2), then we obtain

Proceeding thus one obtains in equation (m − 2) an expression for a_m as a linear combination of the starting values a₁ and a₂ with factors composed of the quotients q_i of the Euclidean algorithm.

In this way we obtain a representation of gcd(a, b) = u · a + v · b =: g as a linear combination of a and b with integer factors u and v, where u modulo a/g and v modulo b/g are uniquely determined. If for an element ā Î we now have gcd(a, n) = 1 = u · a + v · n, then it follows immediately that 1 ≡ u · a mod n, or, equivalently, ā · ū = . In this case u modulo n is uniquely determined, and ū is consequently the inverse of ā in . We have thus found a condition for the existence of a multiplicative inverse of an element in the residue class ring , and we have simultaneously obtained a procedure for constructing such an inverse, which shall demonstrate with the following example. From the calculation above of gcd(723, 288) we obtain by rearrangement

From this we obtain our representation of the greatest common divisor:

click to expand

A fast procedure for calculating this representation of the greatest common divisor would consist in storing the quotients q_i (as is done here on the page) so that they would be available for the backward calculation of the desired factors. Because of the high memory requirement, such a procedure would not be practicable. It is necessary to find a compromise between memory requirements and computational time, which is a typical tradeoff in the design and implementation of algorithms. To obtain a realistic procedure we shall further alter the Euclidean algorithm in such a way that the representation of the greatest common divisor as a linear combination can be calculated along with the greatest common divisor itself. For ā in there exists an inverse Î if gcd(a, n) = 1. The converse of this statement can also be demonstrated: If ā in has a multiplicative inverse, then gcd(a, n) = 1 (one may find a mathematical proof of this statement in [Nive], the proof to Theorem 2.13). We see, then, that here the issue of having no common factors (that is, being relatively prime) is of great significance: If we consider the subset := {ā Î | gcd(a, n) = 1} of those elements ā Î for which a has no common factor with n other than 1, then with the operation of multiplication one has an abelian group, which we have denoted by (, ·) already in Chapter 5. The properties of (, ·) as an abelian semigroup with unit,

associativity of (, ·),
commutativity of (, ·),
existence of a unit: For all ā Î one has ā · = ā,

carry over directly to (, ·). The existence of multiplicative inverses holds because we have selected precisely those elements that have such inverses, so that we have now only to demonstrate closure, namely, that for two elements ā and in the product ā · is again an element of . Closure is easily proved: If a and b are relatively prime to n, then the product of a and b cannot have a nontrivial factor in common with n, so that ā · must belong to the set . The group (, ·) is called the group of residue classes relatively prime to n.

The number of elements in , or, equivalently, the number of integers relatively prime to n in the set {1, 2,...,n − 1 }, is given by the Euler phi function φ(n). For n = written as a product of distinct primes p₁,...,p_t to positive powers e_i, we have

(see, for example, [Nive], Sections 2.1 and 2.4). This means, for example, that has p − 1 elements if p is a prime number.^[1]

If gcd(a, n) = 1, then according to a theorem of Euler, a generalization of the little theorem of Fermat, a^φ(n) ≡ 1 mod n, so that the calculation of a^φ(n)−1 mod n also represents a way to determine the multiplicative inverse of ā.^[2] For example, if n = p · q with prime numbers p ≠ q and a Î , then a^{(p−1)(q−1)} ≡ 1 mod n, and therefore a^{(p−1)(q−1)−1} mod n is the inverse of a modulo n. However, this calculation requires even in the best case that φ(n) be known, a modular exponentiation whose computational cost is O (log³ n).

We do significantly better, namely with a computational cost of O (log² n) and without knowing the value of the Euler phi function, by integrating the above constructive procedure into the Euclidean algorithm. For this we introduce variables u and v, with the help of which the invariants

are maintained in the individual steps of the procedure presented on page 167, in which we have

and these invariants provide us at the end of the algorithm the desired representation of the greatest common divisor as a linear combination of a and b. Such a procedure is called an extended Euclidean algorithm.

The following extension of the Euclidean algorithm is taken from [Cohe], Section 1.3, Algorithm 1.3.6. The variable v in the above invariant condition is employed only implicitly, and only at the end is it calculated as v := (d − u · a)/b.

Extended Euclidean algorithm for calculating gcd(a, b) and factors u and v such that gcd(a, b) = u · a + v · b, 0 ≤ a, b

Set u ← 1, d ← a. If b = 0, set v ← 0 and terminate the algorithm; otherwise, set v₁ ← 0 and v₃ ← b.
Calculate q and t₃ with d = q · v₃ + t₃ and t₃ < v₃ by a division with remainder, and set t₁ ← u − q · v₁, u ← v₁, d ← v₃, v₁ ← t₁, and v₃ ← t₃.
If v₃ = 0, set v ← (d − u · a)/b and terminate the algorithm; otherwise, go to step 2.

The following function xgcd_l() uses the auxiliary functions sadd() and ssub() for the (exceptional) calculation of a signed addition and subtraction. Each of these functions contains a prelude that deals with the sign as an argument to be passed, and then calls the kernel functions add() and sub() (cf. Chapter 5), which execute addition and subtraction, respectively, without consideration of overflow or underflow. Based on the division function div_l() for natural numbers there exists the auxiliary function smod(), which forms the residue a mod b with a, b Î , b > 0. These auxiliary functions will be needed again later, in connection with the application of the Chinese remainder theorem in the function chinrem_l() (see Section 10.4.3). In a possible extension of the FLINT/C library for processing integers they could be used as models for handling signs.

A hint for using the following function is in order: If the arguments satisfy a, b ≥ N_max/2, an overflow in the factors u and v, which are returned as the result of xgcd_l(), can occur. In such cases enough space must be reserved for holding u and v, which are then declared by the calling program as type CLINTD or CLINTQ as required (see Chapter 2).

Function:	extended Euclidean algorithm for calculating the representation gcd(a, b) = u · a + v · b for natural numbers a, b
Syntax:	void xgcd_l (CLINT a_l, CLINT b_l, CLINT g_l, CLINT u_l, int sign_u, CLINT v_l, int sign_v);
Input:	a_l, b_l (operands)
Output:	g_l (gcd of a_l and b_l) u_l, v_l (factors of a_l and b_l in the representation of g_l) sign_u (sign of u_l) sign_v (sign of v_l).

 void xgcd_l (CLINT a_l, CLINT b_l, CLINT d_l, CLINT u_l, int *sign_u, CLINT v_l,                                                            int *sign_v) {   CLINT v1_l, v3_l, t1_l, t3_l, q_l;   CLINTD tmp_l, tmpu_l, tmpv_l;   int sign_v1, sign_t1;

Step 1: Initialization.

   cpy_l (d_l, a_l);   cpy_l (v3_l, b_l);   if (EQZ_L (v3_l))     {       SETONE_L (u_l);       SETZERO_L (v_l);       *sign_u = 1;       *sign_v = 1;       return;     }   SETONE_L (tmpu_l);   *sign_u = 1;   SETZERO_L (v1_l);   sign_v1 = 1;

Step 2: Main loop; calculation of the greatest common divisor and of u.

   while (GTZ_L (v3_l))     {       div_l (d_l, v3_l, q_l, t3_l);       mul_l (v1_l, q_l, q_l);       sign_t1 = ssub (tmpu_l, *sign_u, q_l, sign_v1, t1_l);       cpy_l (tmpu_l, v1_l);       *sign_u = sign_v1;       cpy_l (d_l, v3_l);       cpy_l (v1_l, t1_l);       sign_v1 = sign_t1;       cpy_l (v3_l, t3_l);     }

Step 3: Calculation of v and the end of the procedure.

   mult (a_l, tmpu_l, tmp_l);   *sign_v = ssub (d_l, 1, tmp_l, *sign_u, tmp_l);   div_l (tmp_l, b_l, tmpv_l, tmp_l);   cpy_l (u_l, tmpu_l);   cpy_l (v_l, tmpv_l);   return; }

Since dealing with negative numbers within the FLINT/C package requires additional cost, we arrive at the observation that for calculating the inverse of a residue class ā Î only the one factor u of the representation 1 = u · a + v · n of the greatest common divisor is necessary. A positive representative for u can always be found, and we can thereby spare ourselves the need to deal with negative numbers. The following algorithm is a variant of the previous one that makes use of this observation and eliminates entirely the calculation of v.

Extended Euclidean algorithm for calculating gcd(a, n) and the multiplicative inverse of a mod n, 0 ≤ a, 0 < n

Set u ← 1, g ← a, v₁ ← 0, and v₃ ← n.
Calculate q and t₃ with g = q · v₃ + t₃ and t₃ < v₃ by a division with remainder and set t₁ ← u − q · v₁ mod n, u ← v₁, g ← v₃, v₁ ← t₁, and v₃ ← t₃.
If v₃ = 0, output g as gcd(a, n) and u as the inverse of a mod n and terminate the algorithm; otherwise, return to step 2.

The modular step t₁ ← u − q · v₁ mod n ensures that t₁, v₁, and u do not become negative. At the end we have u Î {1,...,n − 1}. The coding of the algorithm leads us to the following function.

Function:	calculation of the multiplicative inverse in
Syntax:	void inv_l (CLINT a_l, CLINT n_l, CLINT g_l, CLINT i_l);
Input:	a_l, n_l (operands)
Output:	g_l (gcd of a_l and n_l) i_l (inverse of a_l mod n_l, if defined)

 void inv_l (CLINT a_l, CLINT n_l, CLINT g_l, CLINT i_l) {   CLINT v1_l, v3_l, t1_l, t3_l, q_l;

Test of the operands for 0. If one of the operands is zero, then there does not exist an inverse, but there does exist a greatest common divisor (cf. page 166). The result variable i_l is then undefined, which is indicated by being set to zero.

   if (EQZ_L (a_l))     {       if (EQZ_L (n_l))          {            SETZERO_L (g_l);            SETZERO_L (i_l);            return;          }       else          {            cpy_l (g_l, n_l);            SETZERO_L (i_l);            return;          }     }   else     {       if (EQZ_L (n_l))          {            cpy_l (g_l, a_l);            SETZERO_L (i_l);            return;          }     }

Step 1: Initialization of the variables.

   cpy_l (g_l, a_l);   cpy_l (v3_l, n_l);   SETZERO_L (v1_l);   SETONE_L (t1_l);   do     {

Step 2: With the test in GTZ_L (t3_l) after the division an unnecessary call to mmul_l() and msub_l() is avoided in the last run through the loop. The assignment to the result variable i_l is not carried out until the end.

       div_l (g_l, v3_l, q_l, t3_l);       if (GTZ_L (t3_l))          {            mmul_l (v1_l, q_l, q_l, n_l);            msub_l (t1_l, q_l, q_l, n_l);            cpy_l (t1_l, v1_l);            cpy_l (v1_l, q_l);            cpy_l (g_l, v3_l);            cpy_l (v3_l, t3_l);          }     }   while (GTZ_L (t3_l));

Step 3: As the last requisite assignment we take the greatest common divisor from the variable v3_l, and if the greatest common divisor is equal to 1, we take the inverse to a_l from the variable v1_l.

  cpy_l (g_l, v3_l);  if (EQONE_L (g_l))    {      cpy_l (i_l, v1_l);    }  else    {      SETZERO_L (i_l);    } }

^[1]In this case is in fact a field, since both (, +) and (, ·) = ( \ {0}, ·) are abelian groups (see [Nive], Section 2.11). Finite fields have application, for example, to coding theory, and they play an important role in modern cryptography.

^[2]The little Fermat theorem states that for a prime number p and for any integer a one has a^p ≡ a mod p. If p is not a divisor of a, then a^p−1 ≡ 1 mod p (see [Bund], Chapter 2, §3.3). The little theorem of Fermat and its generalization by Euler are among the most important theorems of number theory.

Team-Fly