배타적 논리합과 합동식

 

배타적 논리합(eXclusive OR, XOR)

입력된 두개의 값이 서로 다를 때 '참'을 반환하는 연산자이다.

• 암호학에서는 '비트 단위'로 이뤄짐.
• 연산자: ⊕

• 임의의 정수 x를 자기 자신과 배타적 논리합 하면 결과는 0
  • x ⊕ x = 0

입력		출력
0	0	0
0	1	1
1	0	1
1	1	0

-예시

5⊕7 = (101)₂ ⊕ (111)₂ = (010)₂ = 2

3⊕10 = (0011)₂ ⊕ (1010)₂ = (1001)₂ = 9

2⊕5 = (010)₂ ⊕ (101)₂ = (111)₂ = 7

---

합동식(congruence)

두 정수 a, b를 각각 정수 m으로 나눴을 떄 나머지가 같은지 판별하는 식

합동(congruent)

나머지가 같을 때 수학적으로 a, b가 mod m에 대해 합동이라고 표현함.

 

-예시

1. 7과 17은 10으로 나눈 나머지가 같다 → 7과 17은 mod10에 대해 합동

👉 7≡17(mod 10)

 

2. 12과 5는 3으로 나눈 나머지가 다르다 → 12와 5는 mod3에 대해 합동이 아님

 

• a, b가 mod m에 대해 합동일 경우
  • a, b 각각 정수 x를 덧셈, 뺄셈, 곱셈을 해도 그대로 '합동'
  • 나눗셈의 경우 합동이 되지 않는다.

합동식에서 곱셈의 역원

a, m은 정수일 때 , a×b≡1(mod m)을 만족하는 b를 → mod m에 대한 aa의 곱의 역원이라고 함.

표기) $a^{-1}$

• 역원은 a와 m이 서로소 일 때만 존재함.
• ex) 2×4=8≡1(mod 7)이다. 따라서 mod 7에서 2에 대한 역원은 4이다.

💻 Dreamhack에서 공부한 내용을 정리한 글입니다.