scheme in that dividing a dividend by a divisor results the value of the residue, with the quotient ignored. The (mod) represents a modular operator which have two operands: an integer number and a modulus (n), and results a nonnegative residue. For instance, 15 mod 7 = 1. The operator (mod) gives an integer number between 0 and n − 1, which is constant. The operator (mod) produces a finite set of integer numbers known as residues and the set is defined as Zn [5, 7]. For instance, Zn = {0,1,2,3,…,n − 1}.
4.2.2 Congruence
Instead of equality, the term congruence is sometimes used. The equality maps one-to-one, while the congruence maps many-to-one. The congruent operator (≡) is used to indicate that two integer numbers are compatible. For instance, 1 ≡ 15 (mod 7). By using congruence, all matched integer numbers modulo n are assigned to the identical point on the ring [5].
4.2.3 Modular Arithmetic Operations
Modular number crunching operations have the properties given below for massive numbers [5].
• (ρ + λ) mod θ = [(ρ mod θ) + (λ mod θ)] mod θ.
• (ρ − λ) mod θ = [(ρ mod θ) − (λ mod θ)] mod θ.
• (ρ × λ) mod θ = [(ρ mod θ) × (λ mod θ)] mod θ.
4.2.4 Inverses
Each number in modular number crunching system has an additive counterpart, which is its opposite. The summation of the number and its opposite results to 0 modulo n. In the case of a + b ≡ 0 (mod n) Zn, a and b are the polar opposites of one another [5, 7].
Furthermore, a number may theoretically have a multiplicative inverse known as a reciprocal. The whole number multiplied by its inverse is compatible with 1 modulo n. In the case of a × b ≡ 1(mod n) Zn, a and b are reciprocals of one another [5, 7].
In cryptography, two additional sets are sometimes used: Zp and Zp*, where p is a prime integer. Each member of Zp has its corresponding opposite and reciprocal, but the zero does not have a reciprocal. Each member of Zp* is guaranteed to have both an opposite and a reciprocal [5, 7].
4.3 Complex Plane
4.3.1 Introduction
The plane made of complex numbers is defined as complex plane Z(n) which is a geometrical representation in two dimensions made up of two axes: horizontal one for real and vertical one for imaginary. It has a set of complex numbers with the structure: α + βi, where α for the real one and β for the imaginary one and they are whole numbers in the set. α + βi is a complex number represented as a point which meets at α and β, and exists on Z(n) [10, 14]. A plane made of complex numbers is illustrated in Figure 4.1.
4.3.2 Complex Number Arithmetic Operations and Inverses
For arithmetic operations on complex numbers, the following formula [3, 9, 10] is used. Let u = α1 + β1i, v = α2 + β2i, and w = α + βi.
• u + v = (α1 + α2) + (β1 + β2)i
• u − v = (α1 − α2) + (β1 − β2)i
• u.v = (α1α2 − β1β2) + (α1β2 + α2β1)i
•
•
• k.w = k.α + k.βi, where k is a scalar.
4.4 Matrix Algebra
4.4.1 Introduction
“Residue matrices”, of which all elements are included in Zn, where n represents a prime, are commonly used in cryptography. Modular arithmetic is used to perform all matrix transformations on residue matrices. The properties of “residue matrices” are identical to those of “general matrices”.
Figure 4.1 Complex plane Z(n).
A matrix is defined in computing science by a set in two dimensions including p × q elements, where p represents the number of rows and q represents the number of columns (cols). A matrix is typically represented by a capital character like M. The element mij is assigned in the place which meets at the ith row and the jth col [5].
A matrix with p = 1 is referred to as a row matrix, while one with q = 1 is referred to as “a column matrix”. A matrix with p = q is referred to as “a square matrix” and its elements m11, m22, ----, mqq is referred to as “a main diagonal”. A matrix having all rows and cols which put to 0’s is referred as “an additive identity matrix” and the letter 0 is used to represent it. A square one having 1’s on “the main diagonal” and 0’s somewhere else is referred to as “an identity matrix” and the letter I is used to represent it [5].
If two matrices have the identical number of rows and columns and their corresponding elements are identical, then they are identical. In terms of representation of letters, M = N if they have mij = nij for all i’s and j’s [5].
4.4.2 Matrix Arithmetic Operations
It may be to add and subtract two matrices with the equal number of rows and cols. R = M + N means “addition of two matrices”, M and N. In this case, rij = mij + nij. R = M − N means “subtraction of two matrices”, M and N. In this case, rij = mij − nij [5].
If the quantity of cols in the matrix is identical to the quantity of rows in another matrix, then the two matrices can be multiplied. In this case, if M is a matrix with p × k and N is one with k × q, “the product matrix” of them is a matrix R with p × q. Each element of “the product matrix” R is considered in the way rij = ∑mik × nkj [5].
“Scalar multiplication of a matrix” is defined by multiplying a matrix with a scalar number. If M is a matrix with p × q and β is a scalar number, then R = β × M is a matrix with p × q. In this case, rij = β × mij for each element of the matrix R [5].
4.4.3 Inverses
Determinant.
