LITMIR.BIZ

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].

      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,

Скачать книгу