합동식, 오일러(Euler)함수 [Crypto]

· 합동식

- a 와 b 는 mod m 상에서 합동이다 → a ≡ b mod m

ex) mod 7 상에서 5와 합동인 수를 모두 쓰면? → [5, 12, 19, ...]

 

---

 

· 완전잉여계(Complete Residue System)

- 집합 0, 1, ... , m - 1 을 mod m 상에서의 완전잉여계라고 한다. 즉. % m 연산 결과의 집합, m으로 나눈 나머지 집합이다. 'm'을 다 모아둔 숫자를 완전잉여계라고 한다.

ex) 11의 완전잉여계 원소 = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

'm'의 원소는 모두 몇 개인가? = m개

 

---

 

· 기약잉여계(Reduced Residue System)

- 완전잉여계에서 m과 서로소인 원소의 집합을 기약잉여계라고 한다.

* 서로소 : 두 수의 공약수가 1밖에 없는 수

ex) 8의 기약잉여계 원소 = 1, 3, 5, 7

7의 기약잉여계 원소의 수 = 1, 2, 3, 4, 5, 6 [6개]

- 기약잉여계의 특징 : 기약잉여계 m에 m과 서로소인 a를 곱해도 기약잉여계가 된다.

기약잉여계 특징

 

---

 

· Euler 함수

- Euler 함수는 ϕ m 으로 표시하며, 기약잉여계의 원소의 숫자를 나타낸다.

ex) ϕ1 = 1 >>>  mod 1 = { 0 }

0과 1은 서로소이다.

1은 약수가 1 뿐이다.

0은 모든 수가 약수로 들어갈 수 있다.

공통되는 약수가 1뿐이기 때문에 0이 된다.

2부터는 최대 공약수가 2로 바뀌기 때문에 0이 될 수 없다.

ϕ2 = 1, ϕ3 = 2, ϕ4 = 2, ϕ5 = 4

- 기약잉여계의 특징으로부터 Euler의 정리가 성립한다.

오일러의 정리

- 어떤 수에 a^ϕm을 곱했더니 자기 자신이 나왔다면 오일러의 정리 성립

- Euler의 정리 = a^ϕm = 1 mod m

* 단, 조건은 (gcd(a, m) = 1)이어야 한다.