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

Equation 5.1. 

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,

Equation 5.2. 

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

Equation 5.3. 

(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:

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

Equation 5.4. 

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

Equation 5.5. 

Two residue classes modulo a fixed number m are either the same or disjoint.^[11] 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 mthere 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

(the sum of classes is equal to the class of the sum);

(the product of classes is equal to the class of the product).

Both relations are well-defined, since in each case the result is a residue class modulo m. The set •_m := {

On account of properties 1 through 5 we have that (•_m, +) is an abelian group, where the term abelian refers to the commutativity of addition. From property 4 we can define subtraction in • _m as usual, namely, as addition of the inverse element: If

Equation 5.6. 

In (•_m, •) the group laws 6, 7, 8, and 9 hold for multiplication, where the multiplicative identity is

The significance of an algebraic structure like (

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 R_m := { 0, 1, . . . , m − 1 }. The set of numbers r satisfying −

As an example we consider

Equation 5.7. 

is equivalent to

Equation 5.8. 

while

Equation 5.9. 

is equivalent to

Equation 5.10. 

By identifying the alphabet with the residue class ring

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 5.

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 ≤ N_max. 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 2^k, 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

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 2MAX_B 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 (N_max + 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 36).

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;

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

mult (aa_l, bb_l, p_l);

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 (N_max + 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() formodular arithmetic.

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

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

{
add (a_l, b_l, tmp_l);

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

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.

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

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);

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.

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

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.

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

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.

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

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

Equation 5.11. 

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.

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

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);
}