Cryptography(암호학) - 배타적 논리합과 합동식

오늘은 배타적 논리합, 합동식에 대해 알아볼 것이다.

 

 

1. 배타적 논리합(XOR)

 

배타적 논리합은 XOR이라고도 불리는데 이는 입력으로 들어온 두 입력값(인자)가 다를 경우 True(참)을 반환하는 연산이다.

XOR은 기본적으로 비트단위로 이루어진다. 2진법으로 각 자리 수가 같은면 0, 다르면 1을 반환한다.

 

배타적 논리합 예시

 

반응형

2. 합동식

합동식은 두 정수 x,y를 m으로 나눴을때 나머지가 같은지 확인하는 것이다.

 

x,y를 각각 m으로 나눴을때 같으면, x와 y가 mod m에 대해 합동이라고 한다.

 

예를들어, 13과 3은 10으로 나눴을때 나머지가 같으므로 아래처럼 나타낸다.

13 ≡ 3(mod 10)

그리고 12와 5를 3으로 나눴을때 나머지는 다르므로 아래처럼 나타낸다.

합동이 아니라는 기호가 없어서....

 

만약 a,b가 mod m에 대해 합동이면, 아래 또한 성립한다.

a+x, b+x
a-x, b-x
ax, bx

 

정수 a, m에 대한 ab ≡ 1(mod m)이라면 b는 mod m에 대한  a의 곱의역원이라 불리며, b를 a의 -1승이라고 표현한다.

예를 들어 2×4=8≡1(mod 7)이므로 mod 7에서 2에 대한 역원은 4이다.

 

하지만 역원은 a와 m이 역원일때만 존재한다.