정보보안/Crypto
2022. 8. 3.
[암호학] 암호학을 위한 수리논리
암호학을 배우기 위해 알아야하는 기초적인 수학적 지식을 정리해보려고 합니다. 합동식 합동식은 정수론에서 다루는 분야입니다. 두 정수 a, b에 대하여 각각 정수 m으로 나눴을 때 나머지가 같은지 판별하는 연산인데요. a, b를 m으로 나눈 나머지가 같을 때, a와 b는 mod m에 대해 합동이다. 라고 표현합니다. 예를 들어서, 3과 13은 5로 나눈 나머지가 서로 같습니다. 따라서 3과 13은 mod 5에 대해 합동입니다. 이는 기호로 3 ≡ 13(mod 5)로 나타낼 수 있습니다. 반대로, 3과 14는 mod 5에 대해 합동이 아닙니다. a, b가 mod m에 대해 합동일 경우 a와 b에 동일한 x를 더하거나 빼거나 곱하여도 합동을 유지합니다. 하지만 동일한 x로 나눴을 때에는 합동이 성립하지 않습니..