Handbook of Intelligent Computing and Optimization for Sustainable Development. Группа авторов

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 m₁₁, m₂₂, ----, 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. “The determinant of an equivalent matrix” defined as det(M) for M of size q × q can be designed recursively as given below [5].

       • If q = 1, det(M) = m11.

       • If q > 1, .

      where Mij stands for a matrix M defined by ith row and jth column. The determinant may be found only for an equivalent matrix.

      Additive Inverse. If matrix N is “the additive inverse” of matrix M, then M + N = 0 because their corresponding elements have the property: nij = −mij for all i’s and j’s. The symbol –M is generally used to represent the additive inverse of matrix M [5].

      Multiplicative Inverse. Only square matrices can be used to compute “the reciprocal of a matrix”. Matrix M has a reciprocal of N, resulting in M × N = N × M = I. The symbol M-1 is generally used to represent a reciprocal of M. The matrices have their reciprocals in the case of det(M) ≠ 0 [5].

4.5 Elliptic Curve Arithmetic

      4.5.1 Introduction

      The “elliptic curve” in a finite field known as E(GF) is a curve in cubic-form derived from the Weierstrass equation: y² + β₁xy + β₃y = x³ + β₂x² + β₄x + β₆ in GF. In this case, β_i ∈ GF and GF is a finite field [4].

      The curve E(GF(p)) has the form: y² = x³ + ax + b in which p is a prime greater than 3, a, b ∈ GF(p) and 4a³ + 27b² ≠ 0. (β₁ = β₂ = β₃ = 0; β₄ = a and β₆ = b on the Weierstrass equation) [4].

      4.5.2 Arithmetic Operations on E(GF(p))

Adding points on the curve applies the chord-and-tangent rule and outcomes another point. Adding points on the curve generates an additive group including the point at infinity in symbol O [4]. It is the group of points which are utilized in building cryptosystems using the curve. The description in geometric gives easy understanding. Consider that M = (x₁, y₁) and N = (x₂, y₂) are the points existing on the curve. Suppose that adding M and N results P = (x₃, y₃) on the curve. Adding points is described in Figure 4.2. The tangent line sketching from M to N touches at the point marked by −P. The reflection of −P is P [1, 6]. Consider that doubling a point M results P = (x₃, y₃) on the curve. Doubling a point is described in Figure 4.3. The tangent line sketching from point M touches at the point marked by −P. The reflection of −P is P as in the case of adding points [1, 6].

Figure 4.2 Adding points (P = M + N).

Figure 4.3 Doubling a point (P = M + M).

      The algebraic methods for adding points and doubling a point on E(GF(p)) are followings [4].

       • M + O = O + M = M and M + (−M) = O for any point, M ∈ E(GF(p)). If M = (x, y) ∈ E(GF(p)), then (x, −y) is defined as (−M) which stands for the inverse of M. O is the point at infinity which is known as additive identity.

       • (Adding points). Consider that M, N ∈ E(GF(p)), M = (x1, y1), and N = (x2,