Every fine story must leave in the mind of the sensitive reader an intangible residuum of pleasure...
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:[10]
(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:
(i) 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
.
(ii) 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
.
(iii) 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
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 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
(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 := {
Closure with respect to addition:
The sum of two elements of
For every
Existence of an additive identity:
For every
Existence of an additive inverse:
For each element
For every
Closure with respect to multiplication:
The product of two elements of
Associativity of multiplication:
For every
Existence of a multiplicative identity: For every
Commutativity of multiplication: For each
In (•m, +, •) the distributive law holds:
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
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 Rm := { 0, 1, . . . , m − 1 }. The set of numbers r
satisfying −
As an example we consider
is equivalent to
while
is equivalent to
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 ≤ 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
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 36).
Function: | multiplication |
Syntax: |
|
Input: |
|
Output: |
|
Return: |
|
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;
Purging of leading zeros and support of the accumulator operation.
cpy_l (aa_l, f1_l); cpy_l (bb_l, f2_l);
Call the kernel function for multiplication.
mult (aa_l, bb_l, p_l);
Check for and deal with overflow.
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()
formodular arithmetic.
Function: | modular addition |
Syntax: | int madd_l (CLINT aa_l, CLINT bb_l, CLINT c_l, CLINT m_l); |
Input: |
|
Output: |
|
Return: |
|
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
If a_l
and b_l
both lie below m_l
, then we are spared a division.
{ add (a_l, b_l, tmp_l); if (GE_L (tmp_l, m_l)) { sub_l (tmp_l, m_l, tmp_l); /* underflow excluded */ }
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.
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.
Function: | modular subtraction |
Syntax: | int msub_l (CLINT aa_l, CLINT bb_l, CLINT c_l, CLINT m_l);M |
Input: |
|
Output: |
|
Return: |
|
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);
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
.
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.
Function: | modular multiplication |
Syntax: | int mmul_l (CLINT aa_l, CLINT bb_l, CLINT c_l, CLINT m_l); |
Input: |
|
Output: |
|
Return: |
|
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.
Function: | modular squaring |
Syntax: | int msqr_l (CLINT aa_l, CLINT c_l, CLINT m_l); |
Input: |
|
Output: |
|
Return: |
|
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.
modular addition of a | |
Syntax: | int umadd_l (CLINT a_l, USHORT b, CLINT c_l, CLINT m_l); |
Input: |
|
Output: |
|
Return: |
|
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
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.
Function: | test for equivalence modulo m |
Syntax: | int mequ_l (CLINT a_l, CLINT b_l, CLINT m_l); |
Input: |
|
Return: | 1 if 0 otherwise |
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); }
[10] Carl Friedrich Gauss, 1777 – 1855, 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.
[11] 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.
[12] A semigroup (H, *) exists merely by virtue of there existing on the set H an associative relation *.
[13] See Aulus Gellius, XII, 9 and Suetonius, Caes. LVI.
18.222.167.183