If a is an integer and n is a positive integer, we define a mod n to be the remainder when a is divided by n. The integer n is called the modulus.

**MODULAR
ARITHMETIC**

The Modulus

If *a *is
an integer and *n *is a positive
integer, we define *a *mod *n *to be the remainder when *a *is
divided by *n*. The integer *n *is called the **modulus**. Thus, for any integer *a*, we can rewrite Equation (4.1) as follows:

*a *= *qn *+ *r *0 <=
*r *< *n*; *q *= [*a*/*n** *]

*a *= [*a*/*n *] * *n *+ (*a *mod *n*)

**11
mod 7 ****= ****4; ****- ****11 mod 7 ****= ****3 **

Two integers *a *and
*b
*are said to be **congruent
modulo n**, if (

**73
****‚ ****4 (mod
23); 21 ****‚ ****-****9**** ****(mod 10)**

Note that if *a *K 0 (mod *n*), then *n *| *a*.

Properties of Congruences

Congruences have the following properties:

To demonstrate the first point, if *n *| (*a *- *b*), then (*a *- *b*) = *kn *for some *k*.

So we can write *a *= *b *+ *kn*. Therefore, (*a *mod *n*) = (remainder when *b *+ *kn *is divided by *n*) = (remainder
when *b *is divided by *n*) = (*b *mod *n*).** **

**23 = = 8
(mod 5) because 23 - 8 = 15 = 5 * 3**

**-11
= = 5 (mod 8) because -11 - 5 = -16 = 8 * (-2)**

**81 == 0
(mod 27) because 81 - 0 = 81 = 27 * 3**

The remaining points are as easily proved.

Modular Arithmetic Operations

Note that, by definition (Figure 4.1), the (mod *n*) operator maps all integers
into the set of integers
{0, 1, ... , (*n *- 1)}. This suggests
the question: Can we perform
arithmetic operations within
the confines of this set? It turns out that we can; this technique is known as **modular
arithmetic**.

Modular arithmetic exhibits the following
properties:

** 1.
**[(

** 2.
**[(

** 3.
**[(

We demonstrate the first property. Define (*a *mod *n*) = *r**a *and (*b *mod *n*) = *r**b*.

Then we can write *a *= *r**a *+ *jn *for
some integer *j *and
*b *= *r**b *+ *kn *for
some integer

*k.
*Then

(*a *+ *b*)
mod *n *= (*r**a *+ *jn *+ *r**b *+ *kn*) mod *n*

= (*r**a *+ *r**b *+ (*k *+ *j*)*n*) mod *n*

= (*r**a *+ *r**b*) mod *n*

= [(*a *mod *n*) + (*b *mod *n*)]mod
*n*

The remaining properties are proven as easily. Here are examples of the three properties:

**11
mod 8 =
3; 15 mod 8 = 7**

**[(11
mod 8) + (15 mod 8)] mod 8 = 10 mod 8
= 2**

**(11 + 15) mod 8
= 26 mod 8 = 2**

**[(11
mod 8) - (15 mod 8)] mod 8 = -4 mod 8 = 4**

**(11
- 15) mod 8 = -4 mod 8 = 4**

**[(11
mod 8) * (15 mod 8)] mod 8 = 21 mod 8 = 5**

**(11
* 15) mod 8 = 165 mod 8 = 5**

Exponentiation is performed by repeated
multiplication, as in ordinary arith- metic. (We have more to say about
exponentiation in Chapter 8.)

**To
find 117 ****mod 13, we can proceed as follows:**

**112 ****= 121 K 4
(mod 13)**

**11****4 ****= (11****2****)****2 ****K 4****2 ****K
3 (mod 13)**

**117 ****K 11 ***** ****4
***** ****3 K 132 K 2 (mod 13)**

Thus, the rules for ordinary arithmetic
involving addition, subtraction, and multiplication carry over into modular
arithmetic.

Table 4.2 provides an illustration of modular
addition and multiplication modulo 8. Looking at addition, the results are straightforward, and there is a regular pattern
to the matrix. Both matrices are symmetric about the main diagonal in conformance
to the commutative property of addition and multiplication. As in ordinary addition, there is an additive inverse,
or negative, to each integer
in modu- lar arithmetic. In
this case, the negative of an integer *x *is
the integer *y *such that

(*x *+ *y*) mod 8 = 0. To find the additive
inverse of an integer in the left-hand column, scan across the corresponding row of the matrix to find
the value 0; the integer at the top of that column
is the additive inverse; thus, (2 + 6) mod 8 = 0. Similarly, the entries in the multiplication table
are straightforward. In ordinary arithmetic,
there is a multiplicative inverse, or reciprocal, to each integer. In modular arithmetic mod 8, the
multiplicative inverse of *x *is the integer *y *such that (*x ** *y*) mod 8 = 1 mod 8. Now, to
find the multiplicative inverse of an integer from the multiplication table,
scan across the matrix in the row for that integer to find the value 1; the
integer at the top of that column is the multiplicative inverse; thus, (3 * 3)
mod 8 = 1. Note that not all integers mod 8 have a multiplicative inverse; more about
that later.

Properties of Modular Arithmetic

Define the set Z*n *as the set of nonnegative
integers less than *n*:

This is referred to as the **set of residues**, or **residue classes **(mod *n*). To be more precise, each integer
in Z*n** *represents a residue
class. We can label
the residue classes (mod *n*) as

The residue classes
(mod 4) are

**[0] ****= ****{ ****... ****, ****-****16, ****-****12, ****-****8, ****-****4, 0, 4, 8, 12, 16, ****... ****}**

**[1]
****= ****{ ****... ****, ****-****15, ****-****11, ****-****7, ****-****3, 1, 5, 9, 13, 17, ****... ****}**

**[2]
****= ****{ ****... ****, ****-****14, ****-****10, ****-****6, ****-****2, 2, 6, 10, 14, 18,
****... ****}**

**[3]
****= ****{ ****... ****, ****-****13, ****-****9, ****-****5, ****-****1, 3, 7, 11, 15, 19,
****... ****}**

Of all the integers in a residue class, the
smallest nonnegative integer is the one used to represent the residue class.
Finding the smallest
nonnegative integer to which
*k *is congruent modulo *n *is called
**reducing k modulo n**.

If we perform
modular arithmetic within
Z*n*, the properties shown in Table 4.3
hold for integers in Z*n*. We show in the next section that this implies
that Z*n** *is a com- mutative ring with a multiplicative identity
element.

There is one peculiarity of modular arithmetic that sets it apart from ordinary
arithmetic. First, observe
that (as in ordinary arithmetic) we can write the following:

**if
**(*a *+ *b*) K (*a *+ *c*) (mod *n*) **then ***b *K *c *(mod *n*) **(4.4)**

**(5 ****+ ****23)
****K ****(5 ****+ ****7) (mod 8); 23 ****K ****7(mod 8)**

Equation (4.4) is consistent with the
existence of an additive inverse. Adding the additive inverse of *a *to both sides of Equation (4.4), we have

((-*a*) + *a** *+ *b*) K ((-*a*) + *a** *+ *c*) (mod *n*) *b *K *c *(mod *n*)

However, the following statement is true
only with the attached condition:

**if
**(*a ** *b*) K (*a ** *c*) (mod *n*) **then ***b *K *c *(mod *n*) **if ***a *is relatively prime to *n ***(4.5)**

Recall that two integers are **relatively
prime **if their
only common positive
integer factor is 1. Similar to the case of Equation (4.4), we can say
that Equation (4.5) is

**Table
4.3 **Properties of Modular
Arithmetic for Integers in Z*n*

consistent with the existence of a
multiplicative inverse. Applying the multiplicative inverse of *a *to both sides of Equation (4.5), we have

((*a *- 1)*ab*) K ((*a *- 1)*ac*) (mod
*n*) *b *K *c *(mod *n*)

**To
see this, consider an example in which the condition of Equation (4.5) does not
hold. The integers 6 and 8 are not relatively prime, since they have the common
factor 2. We have the following:**

** **

**6 ***** ****3 ****= ****18 ****K ****2 (mod 8)**

**6
***** ****7 ****= ****42 ****K ****2 (mod 8)**

**Yet
3 ****[ ****7 (mod 8).**

The reason for this strange
result is that for any general
modulus *n*, a multiplier *a *that is applied in turn to the integers
0 through (*n *- 1) will fail to produce a complete set of residues
if *a *and *n *have any factors
in common.

**With a
= 6 and n = 8,**

**Because
we do not
have a complete
set of residues
when multiplying by 6, more
than one integer
in Z _{8} maps
into the same
residue. Specifically, 6 * 0 mod
8 = 6 * 4 mod 8; 6 * 1 mod 8 = 6 * 5 mod 8; and so on. Because this is a
many-to-one mapping, there is not a unique inverse to the multiply operation.
However, if we take a = 5 and n
= 8, whose only common factor is
1,**

**However, if we take a = 5
and n = 8, whose only common factor is 1,**

**The line of residues contains all the
integers in Z8, in a different order.**

In general,
an integer has a multiplicative inverse in Z*n *if
that integer is relatively prime to *n*. Table
4.2c shows that the integers 1, 3, 5, and 7 have a
multiplicative inverse in Z8; but 2, 4, and 6 do not.

Euclidean
Algorithm Revisited

The Euclidean
algorithm can be based on the following theorem: For any nonnegative integer *a *and
any positive integer
*b*,

gcd(*a*, *b*) = gcd(*b*,
*a *mod *b*) **(4.6)**

**gcd(55, 22) = gcd(22, 55 mod 22) = gcd(22, 11) = 11**

To see that Equation
(4.6) works, let *d *= gcd(*a*,
*b*). Then, by the definition of gcd, *d *| *a *and
*d *| *b*.
For any positive integer *b*,
we can express *a *as

*a
*= *kb *+ *r *K *r *(mod *b*) *a *mod *b *= *r*

with *k*, *r *integers.Therefore, (*a *mod *b*) = *a *- *kb *for some integer *k*. But because *d *| *b*, it also divides *kb*.We also have *d *| *a*.Therefore, *d *| (*a *mod *b*).This shows that *d *is a common divisor of *b *and (*a *mod *b*). Conversely, if *d *is a common divisor of
*b *and (*a *mod *b*), then
*d *| *kb *and thus *d *| [*kb *+ (*a *mod *b*)], which is equivalent
to *d *| *a*.Thus, the set of common divisors of *a *and *b *is equal to the set of
common divisors
of *b *and
(*a** *mod *b*).Therefore, the gcd
of one pair is the
same as the gcd of the
other pair, proving the theorem.

Equation (4.6) can be used repetitively to determine
the greatest common divisor.

**gcd(18, 12) = gcd(12, 6)
= gcd(6, 0) = 6**

**gcd(11, 10) = gcd(10, 1)
= gcd(1, 0) = 1**

This
is the same scheme shown in Equation (4.3), which can be rewritten in the
following way.

We can define the Euclidean algorithm
concisely as the following recursive function.

Euclid(a,b)

**if **(b=0) **then return **a;

**else return **Euclid(b, a mod b);

The Extended
Euclidean Algorithm

We now proceed
to look at an extension
to the Euclidean algorithm that will be impor- tant for later computations in the area of finite
fields and in encryption algorithms,
such as RSA. For given
integers *a *and *b*, the extended
Euclidean algorithm not only calculate the greatest
common divisor *d *but
also two additional integers *x *and
*y
*that satisfy the
following equation.

*ax *+ *by *= *d *= gcd(*a*, *b*) **(4.7)**

It
should be clear that *x *and *y *will have opposite signs. Before
examining the algorithm, let us look at some of the values of *x *and *y *when *a *= 42 and *b *= 30.
Note that gcd(42, 30) = 6. Here is a partial table of values3 for 42*x *+ 30*y*.

Observer that all of the entries are
divisible by 6. This is not surprising, because
both 42 and 30 are
divisible by 6,
so every number
of the form 42*x *+ 30*y *= 6(7*x *+ 5*y*) is a multiple of
6. Note also that gcd(42, 30) = 6 appears in the table. In general, it can be shown
that for given integers *a *and *b*, the smallest positive value of *ax *+ *by *is
equal to gcd(*a*, *b*).

Now
let us show how to extend the Euclidean algorithm to determine (*x*, *y*,
*d*) given *a *and *b*. We again go through the sequence of
divisions indicated in Equation (4.3), and we assume that at each step *i *we can find integers *x**i *and *y**i *that satisfy *r**i *= *ax**i *+ *by**i*. We end up with the following sequence.

We need to make several
additional comments here. In each row, we calculate a new remainder *r**i *based on the remainders of the previous two rows, namely *r**i *- 1 and *r**i** *- 2. To start the algorithm, we need values for *r*0 and *r*- 1, which are just *a** *and *b*.
It is then straightforward to determine the required values
for *x *- 1, *y*- 1, *x*0, and *y*0.

We know from the original Euclidean
algorithm that the process ends with a remainder of
zero and that
the greatest common
divisor of a
and b is d = gcd(a, b) = rn. But we also have
determined that Therefore, in Equation (4.7), x
= xn and y = yn.

d =
rn = axn
+ byn.

As
an example, let
us use a = 1759 and b
= 550 and solve for 1759x + 550y = gcd(1759, 550). The
results are shown in Table 4.4. Thus, we have 1759 x (–111) + 550 x 355 =
–195249 + 195250 = 1.

**Table
4.4 **Extended Euclidean Algorithm Example

Result: *d *= 1; *x *=
- 111; *y
*= 355

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security Principles and Practice : One Symmetric Ciphers : Basic Concepts in Number Theory and Finite Fields : Modular Arithmetic |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.