행렬, 일-변수 일차 방정식, 일차 연립 방정식

<행렬(Determinant)>
- 크기가 mXm인 정방행렬 A의 행렬식은 det(A)로 표기되며 다음과 같이 귀납적으로 계산되는 스칼라 값
  1. If m = 1, det(A) = a11
  2. If m>1, det(A) = 시그마 i=l...m일 때 (-1)^(i+j) * aij * det(Aij)
  Where Aij is a matrix obtained from A by deleting the ith row and jth column
- 행렬식은 정방행렬에서만 정의된다

- 소행렬(Minor matrix) Aij
  - 행렬 A에서 i행과 j열의 모든 원소를 제거한 행렬
  - 행렬 A의 크기가 mXm이면, 소행렬 Aij의 크기는 (m-1) X (m-1)이 된다

- 곱셈에 대한 역행렬은 정방행렬에서만 정의된다


<잉여 행렬(Residue Matrices)>
- 암호는 잉여 행렬, 즉 모든 행렬의 원소가 Zn에 속하는 행렬을 사용한다
- 잉여 핼열은 gcd(det(A), n) = 1이면 곱셈에 대한 역행렬을 가진다

- Zn 상의 원소로 이루어진 mXm(정방) 잉여행렬 A
  B = A^(-1) = det(A)^(-1) * C^r
  1. det(A) 계산
     gcd(det(A), n)가 1이 아니면, 역행렬이 존재하지 않는다(계산 중단)
  2. det(A)의 곱셈에 대한 역원(det(A)^(-1))을 계산
  3. A의 여인수 행렬(Cofactor matrix) C 계산
  4. 여인수 행렬 C의 전치행렬(Transpose of C, C^t)계산
  5. det(A)^(-1)과 C^t의 (스칼라) 곱 계산 
*전치 행렬 : mXn 행렬의 열과 행을 바꾼 nXm의 행렬
*여인수 행렬 : 소행렬식을 이용한 행렬
  - 행렬A가 존재하고 mij일 때, 여인수 행렬[Aij]의 원소 -> Aij = (-1)^(i+j) det(mij)
*수반 행렬 : 여인수 행렬에 대한 전치행렬
*가역 행렬(Invertible matrix) : 역행렬이 존재하는 행렬
*특이 행렬(Singular matrix) : 역행렬이 존재하지않는 행렬로 행렬식이 0인 경우

- 딸림 행렬(adjugate matrix) : 여인수 행렬(Confactor matrix)의 전치행렬


<합동(Congruence)>
- 두 행렬이 열과 행의 개수가 같고 모든 대응되는 원소가 모듈로 n에 대하여 합동이면,
  그 두 행렬은 모듈로 n에 대하여 합동이라고 하고, 
  A=B mod n 라고 표기한다
- 모든 i와 j에 대해 aij 합동 bij mod n 이면, A는 B mod n과 합동이다



<일-변수 일차 방정식(Singel-Variable Linear Equations)>
- 변수가 하나인 방정식, 즉 ax는 b와 합동(mod n)형태의 방정식
- 이러한 형식의 방정식은 해가 없거나 유한개의 해를 가진다
  Assume that the gcd(a, n) = d
  If d not | b, there is no solution
  If d|b, there an d solultions


<일차 연립 방정식(Set of Linear Equations)>
- 같은 모듈러에 대한 일차방정식 집합에서, 변수의 계수로 구성된 행렬의 역행렬이 존재하면(Invertible)
  그 방정식 집합을 풀 수 있다