[수학] 모듈러 연산

alg0r1thm·2022년 4월 27일

0

[밑바닥부터 시작하는 비트코인] 의 유한체를 공부하는 과정에서 모듈러 연산에 대한 정리가 필요했기 때문에 따로 문서를 작성했다.

1.1 모듈러 연산의 필요성

크게 유한체는 다른 연산 형식도 가능하나 주로 모듈러 연산에 적용시켜 표현하는 경우가 많다.
나머지 연산에 대해 알고 싶다면 모듈러 연산의 원리를 이해하여 보다 쉽게 알 수 있다.

1.2 모듈러 연산

모듈러 연산에 관한 성질을 증명하고자 할 때 나머지 정리를 주로 활용한다.
나머지 정리
- 어떠한 정수 $A$ 와 양의 정수 $B$ 가 주어질때 유일한 정수 $Q$ 와 $R$ 은 다음을 만족한다.
  $A = B×Q+R, \leq R < B$
이는 나눗셈을 통하여 직관적으로 이해 할 수 있다.
$A$ 를 $B$ 로 나누면 $Q$ 는 몫이고 $R$ 은 나머지 이다.
이러한 형태로 어떤 숫자를 표현한다면 아래와 같이 표현할 수 있다.

A\ mod\ B = R

예시를 통해 연산에 대해 직관적으로 표현하면 아래와 같다

A = 7 \ , B=2\ 일때,\\ 7=2\ ×\ 3+1\ \\ 7\ mod\ 2 =1

1.3 모듈러 연산의 덧셈과 뺄셈

모듈러 연산의 덧셈 성질은 아래와 같다.

(A+B)\ mod\ C=(A\ mod\ C + B\ mod\ c)\ mod\ C

예시를 통해 위 식이 성립하는지 검증해보자.

A=14,\ B=17,\ C=5\ 라고\ 할\ 때,\\ (A+B)\ mod\ C=\ (A\ mod\ C+B\ mod\ C)\ mod\ C

LHS = 식의 왼쪽 변
RHS = 식의 오른쪽 변

LHS=(A+B)\ mod\ C \\ LHS = (14+17)\ mod\ 5 \\ LSH=31\ mod\ 5 \\LSH=1

RHS=(A\ mod\ C+B\ mod\ C)\ mod\ C \\RHS = (14\ mod\ 5+17\ mod\ 5)\ mod\ 5\\ RHS=(4+2)\ mod\ 5 \\ RHS=1

\therefore LSH=RHS=1

뺄셈에서도 동일하게 적용할 수 있다.

(A-B)\ mod\ C=(A\ mod\ C + (-B\ mod\ C))\ mod\ C

1.4 모듈러 연산의 곱셈

모듈러 연산의 곱셈 성질은 아래와 같다.

(A\ ×\ B)\ mod\ C = (A\ mod\ C\ ×\ B\ mod\ C)\ mod\ C

예시를 통해 위 식이 성립하는지 검증해보자.

A=4,\ B=7,\ C=6\ 라고\ 할\ 때, \\(A\ ×\ B)\ mod\ C = (A\ mod\ C\ ×\ B\ mod\ C)\ mod\ C

LHS = 식의 좌변
RHS = 식의 우변

LHS=(A\ ×\ B)\ mod\ C \\ LHS=(4\ ×\ 7)\ mod\ 6 \\ LHS = 28\ mod\ 6 \\ LHS = 4

RHS=(A\ mod\ C\ ×\ B\ mod\ C)\ mod\ C \\ RHS=(4\ mod\ 6\ ×\ 7\ mod\ 6)\ mod\ 6 \\ RHS=(4\ ×\ 1)\ mod\ 6 \\ RHS=4\ mod\ 6 \\ RHS=4

\therefore LSH=RHS=4

블록체인 한입

이전 포스트

[밑바닥부터 시작하는 비트코인] 3. 타원곡선 암호

다음 포스트

[수학] 페르마의 소정리

0개의 댓글