암호학 기초 - 3

 

합동식의 특징

a, b 가 mod m 에 대해 합동인 경우 a, b 에 어떠한 정수 x 를 더하거나 빼거나 곱해도 합동이다.

 

다음의 특징을 식으로 나타내면 아래와 같이 된다.

Dreamhack - Cryptography

 

하지만 나눗셈에 대해서는 성립하지 않는다.

 

다음의 특징을 식으로 나타내면 아래와 같이 된다.

Dreamhack - Cryptography

< 단, mod m 에서 m의 값을 x 로 나누는 경우 가능함(추가적인 조건 필요) >

 

 

 

합동식에서의 곱셈의 역원

역원이란?

→ 어떤 수를 곱했을 때 1이 되는 수를 말한다.

정수 a, m에 대해 a×b≡1(mod m) 을 만족하는 b 를 mod m 에 대한 a의 곱의 역원이라고 부르며 a^(-1) 로 표시한다.

위의 식에서 x^(-1) 을 합동식의 곱셈의 역원이라고 한다.

 

위의 예시에서 숫자 8은 2와 4의 곱으로 표현 할 수 있고 숫자 2와 7 모두 서로소이므로

4를 mod 7에 대한 2의 곱의 역원 이라고 말할 수 있다.

 

 

 

Dreamhack - Cryptography 공부내용 정리

https://dreamhack.io/

관련된 문제는 사이트에 수록되어 있습니다