공개키 - 오일러함수, 소인수분해, 거듭제곱

1. 오일러 함수[ Ø(n) ]

- 어떤 자연수 n에 n이하의 자연수 중 n과 서로소인 수를 대응시키는 함수.

- 소수의 경우 Ø(n)는 n-1개 이다. ex) Ø(7) = 6개 (7과 서로소인 1, 2, 3, 4, 5, 6)

 

2. 소인수분해의 특징

p x q => n             p와 q를 알고 n을 구하는 것[암호화]은 쉬우나,

n => p x q             n을 알고 p와 q를 구하는 것[복호화]는 어렵다.

 

3. 거듭제곱

5¹ mod 23 = 5

5² mod 23 = 2

5³ mod 23 = (5¹ mod 23) x (5² mod 23) = 10

5⁴ mod 23 = (5² mod 23) x (5² mod 23) = 4