Cryptography | 배타적 논리합과 합동식

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

입력값으로 들어온 2개의 인자가 서로 다를 때, 참을 반환하는 연산

주로 비트 연산으로 이루어짐 (2진법)

 

▶ 2개의 입력값을 2진법으로 표기, 각 자릿수 값이 다르면 1(참) / 같으면 0(거짓)

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

 

예시)

$5\oplus7 = 101_2 \oplus 111_2 = 010_2 = 2$

$3\oplus10 = 0011_2 \oplus 1010_2 = 1001_2 =9$

 

📌 합동식

두 정수 a, b 를 각각 정수 m으로 나눴을 때 나머지가 같은 식

 

▶ a와 b 각각을 m으로 나눈 나머지가 같을 때, a와 b가 mod m에 대해 합동(congruent)이라 표현

 

예시1)

7과 17은 10으로 나눈 나머지가 같으므로 

7과 17은 mod 10에 대해 합동 ▶ $7 \equiv 17 \pmod{10}$

 

예시2)

12와 5는 3으로 나눈 나머지가 다르므로

12와 5는 mod 3에 대해 합동이 아님 ▶ $12 \not\equiv5 \pmod{3}$ 

 

 

➕ a, b가 mod m에 대해 합동

 

▶ mod m 각각에 정수 x를 더하거나 빼거나 곱해도 합동

 

$ a \equiv b \pmod{m} \Rightarrow \begin{cases} a + x \equiv b + x \pmod{m} \\ a - x \equiv b - x \pmod{m} \\ ax \equiv bx \pmod{m} \end{cases}$

 

▶ 나눗셈은 성립 X

$ a \equiv b \pmod{m} \nRightarrow \frac {a}{x} \equiv \frac {b}{x} \pmod{m}$

 

🔎 합동식에서 곱셈의 역원
정수 a, m에 대해 $a \times b \equiv 1 \pmod{m}$ 을 만족하는 b
▶mod m 에 대한 a의 곱의 역원 , $a^{-1}$

예시 ) $2 \times 4 = 8 \equiv 1 \pmod{7}$
4는 mod 7에서 2에 대한 역원

※ 역원은 a와 m이 서로소일 때만 존재