Chapter 5: Modular Arithmetic: Calculating with Residue Classes

Team-Fly

Every fine story must leave in the mind of the sensitive reader an intangible residuum of pleasure...

Willa Cather, Not Under Forty, "Miss Jewett"

WE BEGIN THIS CHAPTER WITH a discussion of the principle of division with remainder. In relation to this we shall explain the significance of these remainders, their possible applications, and how one calculates with them. In order for the functions to be introduced later to be understandable, we begin with a bit of algebra.

We have seen that in division with remainder of an integer a Î by a natural number 0 < m Î one has the unique representation

Here r is called the remainder after division of a by m or the residue of a modulo m, and it holds that m divides a r without remainder, or in mathematical notation,

This statement about divisibility was given a new notation by Gauss, in analogy to the equal sign:[1]

(say "a is congruent to r modulo m").

Congruence modulo a natural number m is an equivalence relation on the set of natural numbers. This means that the set R := { (a, b) | a b mod m } of integer pairs satisfying m | (a b) has the following properties, which result immediately from division with remainder:

  1. R is reflexive: For all integers a it holds that (a, a) is an element of R, that is, we have a a mod m.

  2. R is symmetric: If (a, b) is in R, then so is (b, a); that is, a b mod m implies b a mod m.

  3. R is transitive: If (a, b) and (b, c) are in R, then so is (a, c); that is, a b mod m and b c mod m implies a c mod m.

The equivalence relation R partitions the set of integers into disjoint sets, called equivalence classes: Given a remainder r and a natural number m > 0 the set

or, in other notation, r + m, is called the residue class of r modulo m. This class contains all integers that upon division by m yield the remainder r.

Here is an example: Let m = 7, r = 5; then the set of integers that upon division by 7 yield the remainder 5 is the residue class

click to expand

Two residue classes modulo a fixed number m are either the same or disjoint.[2] Therefore, a residue class can be uniquely identified by any of its elements. Thus the elements of a residue class are called representatives, and any element can serve as representative of the class. Equality of residue classes is thus equivalent to the congruence of their representatives with respect to the given modulus. Since upon division with remainder the remainder is always smaller than the divisor, for any integer m there can exist only finitely many residue classes modulo m.

Now we come to the reason for this extensive discussion: Residue classes are objects with which one can do arithmetic, and in fact, by employing their representatives. Calculating with residue classes has great significance for algebra and number theory and thus for coding theory and modern cryptography. In what follows we shall attempt to clarify the algebraic aspects of modular arithmetic.

Let a, b, and m be integers, m > 0. For residue classes ā and modulo m we define the relations "+" and "·", which we call addition and multiplication (of residue classes), since they are based on the like-named operations on the integers:

click to expand

Both relations are well-defined, since in each case the result is a residue class modulo m. The set := { | r is a residue modulo m } of residue classes modulo m together with these relations forms a finite commutative ring (, +, ·) with unit, which in particular means that the following axioms are satisfied:

  1. Closure with respect to addition:

    The sum of two elements of is again in .

  2. Associativity of addition:

    For every ā, , in one has ā + ( + ) = (ā + ) + .

  3. Existence of an additive identity:

    For every ā in one has ā + = ā.

  4. Existence of an additive inverse:

    For each element ā in there exists a unique element in such that ā + = .

  5. Commutativity of addition:

    For every ā, in one has ā + = + ā.

  6. Closure with respect to multiplication:

    The product of two elements of is again an element of .

  7. Associativity of multiplication:

    For every ā, , in one has ā · ( ) = (ā · ) · .

  8. Existence of a multiplicative identity: For every ā in one has ā · = ā.

  9. Commutativity of multiplication: For each ā, in one has ā · = · ā.

  10. In (, +, ·) the distributive law holds: ā · ( + ) = ā · + ā · .

On account of properties 1 through 5 we have that (, +) is an abelian group, where the term abelian refers to the commutativity of addition. From property 4 we can define subtraction in as usual, namely, as addition of the inverse element: If is the additive inverse of , then + = , and so for each ā Î we may define

In (, ·) the group laws 6, 7, 8, and 9 hold for multiplication, where the multiplicative identity is . However, in it does not necessarily hold that each element possesses a multiplicative inverse, and thus in general, (, ·) is not a group, but merely a commutative semigroup with unit.[3] However, if we remove from all the elements that have a common divisor with m greater than 1, we then obtain a structure that forms an abelian group with respect to multiplication (see Section 10.2). This structure, which in particular does not contain , is denoted by (, ·).

The significance of an algebraic structure like (, ·), in view of the results we have obtained thus far, can be illustrated by looking at some other well-known commutative rings: The set of integers , the set of rational numbers , and the set of real numbers are commutative rings with unit (in fact, the real numbers form a field, indicating additional internal structure), with the difference that these rings are not finite. The rules for computation that we have outlined above for our finite ring are well known to us because we use them every day. We shall return to these laws in Chapter 12. There they will prove to be trusty allies when it comes to testing arithmetic functions. In this chapter we have collected some important prerequisites.

For calculating with residue classes we rely completely on the classes' representatives. For each residue class modulo m we select precisely one representative and thereby form a complete residue system, in terms of which all of our calculations modulo m can be carried out. The smallest nonnegative complete residue system modulo m is the set Rm := {0, 1,..., m 1}. The set of numbers r satisfying m < r m will be called the smallest absolute complete residue system modulo m.

As an example we consider = {}. The smallest nonnegative residue system modulo 26 is R26 = {0, 1,...,25}, and the smallest absolute residue system modulo 26 is the set {12, 11,...,0, 1,...,13}. The relation between arithmetic with residue classes and modular arithmetic with residue systems can be clarified as follows:

is equivalent to

while

is equivalent to

By identifying the alphabet with the residue class ring or the set of ASCII characters with we can calculate with characters. A simple encoding system that adds a constant from to each letter of a text is ascribed to Julius Caesar, who is said to have preferred the constant . Each letter of the alphabet would thereby be shifted one position to the right, with X moving to A, Y to B, and Z to C.[4]

Calculation in residue class rings can be made clearer by employing composition tables, which we present in Tables 5.1 and 5.2 for the operations "+" and "·" in :

Table 5.1: Composition table for addition modulo 5

+

0

1

2

3

4

0

0

1

2

3

4

1

1

2

3

4

0

2

2

3

4

0

1

3

3

4

0

1

2

4

4

0

1

2

3

Table 5.2: Composition table for multiplication modulo 5

·

0

1

2

3

4

0

0

0

0

0

0

1

0

1

2

3

4

2

0

2

4

1

3

3

0

3

1

4

2

4

0

4

3

2

1

The fact that the set of residue classes is finite gives the nice advantage over infinite structures, such as the ring of integers, that the representation of the results of arithmetic expressions within a computer program will not cause overflow if in forming residues a suitable class representative is chosen. This operation, as executed for example by the function mod_l(), is called reduction (modulo m). We can thus calculate to our hearts' content with the bounded representation of numbers and the functions of the FLINT/C package within a complete residue system modulo m, so long as we have m Nmax. We always choose positive representatives and rely on nonnegative residue systems. Because of these properties of residue classes the FLINT/C package does very well with the CLINT representation of large numbers, except for a few situations, which we shall discuss in some detail.

So much for the theory of the arithmetic of residue classes. Now we shall develop our functions for modular arithmetic. We first recall the functions mod_l() and mod2_l() from Section 4.3, which return the remainder of a reduction modulo m, respectively modulo 2k, and we shall deal in turn with modular addition and subtraction, as well as modular multiplication and squaring. Because of its particular complexity, we devote a separate chapter to modular exponentiation. We shall avoid the notation ā for a residue class by simply omitting the bar and letting the representative a denote the class of a, provided that there is no chance of confusion.

The process by which the functions for modular arithmetic operate consists essentially in carrying out the corresponding nonmodular function on the operands and then using division with remainder to carry out a modular reduction. However, one must note that intermediate results can grow to a size of 2MAXB digits, which due to their size or, in the case of subtraction, on account of a negative sign, cannot be represented in a CLINT object. We have previously called these situations respectively overflow and underflow. The basic arithmetic functions possess mechanisms for dealing with situations of overflow and underflow that reduce these intermediate results modulo (Nmax +1) (see Chapters 3 and 4). These would be effective here if the result of the complete modular operation were representable by a CLINT type. In order to obtain correct results in these cases, we shall extract from the functions that we already have for the basic operations, as announced in Chapter 4, kernel functions

   void add (CLINT, CLINT, CLINT);   void sub (CLINT, CLINT, CLINT);   void mult (CLINT, CLINT, CLINT);   void umul (CLINT, USHORT, CLINT);   void sqr (CLINT, CLINT); 

The kernel functions comprise the arithmetic operations that have been removed from the functions add_l(), sub_l(), mul_l(), and sqr_l(), which we have met earlier. What remains in these functions are simply the processes of removing leading zeros, supporting the accumulator operation, and handling possible overflow or underflow, while for the actual arithmetic operations the kernel functions are invoked. The syntax and semantics of these earlier functions are not altered, and the functions can be used as described.

As an example of multiplication mul_l(), this process leads to the following function (see in this regard the implementation of the function mul_l() on page 35).

start sidebar

Function:

multiplication

Syntax:

int mul_l (CLINT f1_l, CLINT f2_l, CLINT pp_l);

Input:

f1_l, f2_l (factors)

Output:

pp_l (product)

Return:

E_CLINT_OK if all is ok

E_CLINT_OFL if overflow

end sidebar

 int mul_l (CLINT f1_l, CLINT f2_l, CLINT pp_l) {   CLINT aa_l, bb_l;   CLINTD p_l;   int OFL = E_CLINT_OK; 

start sidebar

Purging of leading zeros and support of the accumulator operation.

end sidebar

   cpy_l (aa_l, f1_l);   cpy_l (bb_l, f2_l); 

start sidebar

Call the kernel function for multiplication.

end sidebar

   mult (a_l, b_l, p_l); 

start sidebar

Check for and deal with overflow.

end sidebar

   if (DIGITS_L (p_l) > (USHORT)CLINTMAXDIGIT)    /* overflow ? */     {       ANDMAX_L (p_l);    /* reduce modulo (Nmax + 1) */       OFL = E_CLINT_OFL;     }   cpy_l (pp_l, p_l);   return OFL; } 

For the remaining functions add_l(), sub_l(), and sqr_l() the changes are similar. The arithmetic kernel functions themselves contain no new components and therefore do not need to be given here. For details look at the implementation in flint.c.

The kernel functions do not allow overflow, and they execute no reduction modulo (Nmax + 1). They are intended for internal use by the FLINT/C functions and therefore are declared as static. In using them, however, one must note that they are not equipped for dealing with leading zeros and that they cannot be used in accumulator mode (see Chapter 3).

The use of sub() presupposes that the difference is positive. Otherwise, the result is undefined; there is no control in sub() in this regard. Finally, the calling functions must make available enough space for the result of oversized intermediate results. In particular, sub() requires that the result variable have available at least enough storage space as for the representation of the minuend. We are now equipped to develop the functions madd_l(), msub_l(), mmul_l(), and msqr_l() for modular arithmetic.

start sidebar

Function:

modular addition

Syntax:

 int madd_l (CLINT aa_l, CLINT bb_l, CLINT c_l,                CLINT m_l); 

Input:

aa_l, bb_l (summands), m_l (modulus)

Output:

c_l (remainder)

Return:

E_CLINT_OK if all is ok

E_CLINT_DBZ if division by 0

end sidebar

 int madd_l (CLINT aa_l, CLINT bb_l, CLINT c_l, CLINT m_l) {   CLINT a_l, b_l;   clint tmp_l[CLINTMAXSHORT + 1];   if (EQZ_L (m_l))     {       return E_CLINT_DBZ;     }   cpy_l (a_l, aa_l);   cpy_l (b_l, bb_l);   if (GE_L (a_l, m_l) || GE_L (b_l, m_l))     {       add (a_l, b_l, tmp_l);       mod_l (tmp_l, m_l, c_l);     }   else 

start sidebar

If a_l and b_l both lie below m_l, then we are spared a division.

end sidebar

     {       add (a_l, b_l, tmp_l);       if (GE_L (tmp_l, m_l))          {            sub_l (tmp_l, m_l, tmp_l);    /* underflow excluded */          } 

start sidebar

In the preceding call by sub_l() some care was taken: We supply sub_l() with the argument tmp_l, which here as the sum of a_l and b_l is possibly one digit larger than allowed by the constant MAXB. Within the function sub_l() nothing can go awry as long as we provide storage space for an additional digit in the result. Therefore, we let the result be stored in tmp_l and not immediately in c_l, as one might suppose. Because of these conditions, at the end of sub_l() we have that tmp_l has at most MAXB digits.

end sidebar

       cpy_l (c_l, tmp_l);     }   return E_CLINT_OK; } 

The function for modular subtraction msub_l() uses only the positive intermediate results of the functions add_l(), sub_l(), and mod_l(), in order to remain within a positive residue system.

start sidebar

Function:

modular subtraction

Syntax:

 int msub_l (CLINT aa_l, CLINT bb_l, CLINT c_l,                 CLINT m_l); 

Input:

aa_l (minuend), bb_l (subtrahend), m_l (modulus)

Output:

c_l (remainder)

Return:

E_CLINT_OK if all is ok

E_CLINT_DBZ if division by 0

end sidebar

 int msub_l (CLINT aa_l, CLINT bb_l, CLINT c_l, CLINT m_l) {   CLINT a_l, b_l, tmp_l;   if (EQZ_L (m_l))     {       return E_CLINT_DBZ;     }   cpy_l (a_l, aa_l);   cpy_l (b_l, bb_l); 

start sidebar

We distinguish the cases a_l b_l and a_l < b_l. The first case is a standard situation; in the second case we compute (b_l a_l), reduce modulo m_l, and subtract a positive remainder from m_l.

end sidebar

   if (GE_L (a_l, b_l))    /* a_l  b_l  0 */     {       sub (a_l, b_l, tmp_l);       mod_l (tmp_l, m_l, c_l);     }   else    /* a_l  b_l < 0 */     {       sub (b_l, a_l, tmp_l);       mod_l (tmp_l, m_l, tmp_l);       if (GTZ_L (tmp_l))          {            sub (m_l, tmp_l, c_l);          }       else          {            SETZERO_L (c_l);          }     }   return E_CLINT_OK; } 

Now come the functions mmul_l() and msqr_l() for modular multiplication and squaring, of which we show only that for multiplication.

start sidebar

Function:

modular multiplication

Syntax:

 int mul_l (CLINT aa_l, CLINT bb_l, CLINT c_l,               CLINT m_l); 

Input:

aa_l, bb_l (factors), m_l (modulus)

Output:

c_l (remainder)

Return:

E_CLINT_OK if all ok

E_CLINT_DBZ if division by 0

end sidebar

 int mmul_l (CLINT aa_l, CLINT bb_l, CLINT c_l, CLINT m_l) {   CLINT a_l, b_l;   CLINTD tmp_l;   if (EQZ_L (m_l))     {        return E_CLINT_DBZ;     }   cpy_l (a_l, aa_l);   cpy_l (b_l, bb_l);   mult (a_l, b_l, tmp_l);   mod_l (tmp_l, m_l, c_l);   return E_CLINT_OK; } 

The functions for modular multiplication and squaring are so similar that for modular multiplication we give only the interface of the function.

start sidebar

Function:

modular squaring

Syntax:

int msqr_l (CLINT aa_l, CLINT c_l, CLINT m_l);

Input:

aa_l (factor), m_l (modulus)

Output:

c_l (remainder)

Return:

E_CLINT_OK if all is ok

E_CLINT_DBZ if division by 0

end sidebar

To each of these functions (of course, with the exception of squaring) there is a corresponding mixed function, which as its second argument takes a USHORT argument. As an example, we demonstrate the function umadd_l(). The functions umsub_l() and ummul_l() follow exactly the same pattern, and so we shall not go into them in detail.

start sidebar

Function:

modular addition of a CLINT type and a USHORT type

Syntax:

 int umadd_l (CLINT a_l, USHORT b, CLINT c_l,                CLINT m_l); 

Input:

a_l, b (summands), m_l (modulus)

Output:

c_l (remainder)

Return:

E_CLINT_OK if all is ok

E_CLINT_DBZ if division by 0

end sidebar

 int umadd_l (CLINT a_l, USHORT b, CLINT c_l, CLINT m_l) {   int err;   CLINT tmp_l;   u2clint_l (tmp_l, b);   err = madd_l (a_l, tmp_l, c_l, m_l);   return err; } 

Our collection of mixed functions with a USHORT argument will be extended in the following chapter to include two further functions. To end this chapter we would like, with the help of modular subtraction, to construct an additional useful auxiliary function that determines whether two CLINT values are equal as representatives of a residue class modulo m. The following function mequ_l() accomplishes this by using the definition of the congruence relationship a b mod m m | (a b).

To determine whether two CLINT objects a_l and b_l are equivalent modulo m_l, we need do nothing further than apply msub_l(a_l, b_l, r_l, m_l) and check whether the remainder r_l of this operation is equal to zero.

start sidebar

Function:

test for equivalence modulo m

Syntax:

int mequ_l (CLINT a_l, CLINT b_l, CLINT m_l);

Input:

a_l, b_l (operands), m_l (modulus)

Return:

1 if (a_l == b_l) modulo m_l

0 otherwise

end sidebar

 int mequ_l (CLINT a_l, CLINT b_l, CLINT m_l) {   CLINT r_l;   if (EQZ_L (m_l))     {       return E_CLINT_DBZ;     }   msub_l (a_l, b_l, r_l, m_l);   return ((0 == DIGITS_L (r_l))?1:0); } 

[1]Carl Friedrich Gauss, 17771855, is to be counted among the greatest mathematicians of all time. He made many significant discoveries in mathematics as well as in the natural sciences, and in particular, at the age of 24 he published his famous Disquisitiones Arithmeticae, which is the foundation upon which modern number theory has been built.

[2]Two sets are said to be disjoint if they have no elements in common, or put another way, if their intersection is the empty set.

[3]A semigroup (H, *) exists merely by virtue of there existing on the set H an associative relation *.

[4]See Aulus Gellius, XII, 9 and Suetonius, Caes. LVI.


Team-Fly


Cryptography in C and C++
Cryptography in C and C++
ISBN: 189311595X
EAN: 2147483647
Year: 2001
Pages: 127

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net