Systems of Linear Congruences—Single Modulus - Introduction to Cryptography with Java Applets - page 124

CHAPTER 6

Systems of Linear Congruences—
Single Modulus

In this chapter we will discuss systems of linear congruences. The systems we consider
will be of two types:

1.

Multiple linear congruences consisting of several variables, modulo a single modulus.

2.

Multiple linear congruences consisting of a single variable, modulo different moduli.

Here, we discuss systems of type 1. For these types of systems, you should know how
to handle systems of equations, as well as matrices. Take the following example of a sys-
tem of linear congruences with multiple variables modulo a single modulus:

x y z

5 + 3 + 2 2 (mod 7)

3 x + 4 y + 6 z 1 (mod 7) (*)

2 x + y + z 4 (mod 7)

6.1

MODULAR MATRICES
Note that we can write this in matrix notation as AX B (mod 7) where A is

532
346
211

X is the column vector

x
y
z

and B is the vector

2
1
4