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

Proof. Suppose the matrices are as stated. Note that the i , j th entries in the product matri-
ces AC and BC are a i , t c t , j and b i , t c t , j , respectively. Since A B (mod m ), we have a i , t
b i , t (mod m ) ∀ i and t , and so

a i , t c t , j b i , t c t , j (mod m )

by proposition 20, which says congruent items (mod m ) can be added to both sides of a

congruence (mod m ) and preserve the congruence. Thus, AC BC (mod m ). The proof that

DA BA (mod m ) is nearly identical to the previous; you are invited to do it.

Java Algorithm. In this chapter we discussed modular arithmetic and congruences for
matrices. This is a perfect opportunity to define a useful class for these purposes. We can
call it the ModMatrix class; it represents a matrix whose elements are all taken modulo m .
ModMatrix objects need not be square; we will define how to add, subtract, and multi-
ply them. There will be exceptions thrown if the matrices are of the improper size. Of course,
matrices are not invertible unless they are square (and sometimes not even then), so we will
develop a subclass of ModMatrix called ModSquareMatrix. It will have the appropriate
methods for inverting matrices. Finally, we will also define a ModIdentityMatrix class,
which extends ModSquareMatrix.
First, the ModMatrix class: its data items will consist of a two dimensional array of Big-
Integers, a BigInteger representing the modulus, and ints to record the number of rows and
number of columns in the matrix.

import java.math.BigInteger;
import java.security.*;
public class ModMatrix {
//A ModMatrix is a 2D array of BigIntegers
BigInteger[][] array;

//Number of columns/rows recorded here
int numRows, numCols;

//The modulus of the ModMatrix
BigInteger modulus;

The ModMatrix constructors are of different types. The first produces either a matrix of
all zeros or of random entries, the second reads a one-dimensional array into a two-dimen-
sional matrix, and the third simply copies another matrix. The last constructor is the default
constructor, which accepts no arguments. It does nothing, but is used by the subclasses we
define.

//Creates a matrix with random entries having r rows, c columns,
//Or, it creates a matrix of all zeros
//Matrices start indexing at 1,1. Zeroth column and row are not used.
public ModMatrix(int r,int c,BigInteger m,boolean makeZero) {
SecureRandom sr=new SecureRandom();
modulus=m;
array=new BigInteger[r+1][c+1];