2. 암호학

1. 거듭제곱 구하기

2. RSA 암호 방식

- 합성수의 소인수 분해의 어려움을 이용한다.

이때 합성수는? 소수들의 곱으로 이루어진 수

백 자리 이상의 두개의 소수 p, q를 선택하여 n = p, q를 선택하여 n = p * q를 계산

곱셈은 쉽지만 소인수분해는 어려운 점을 이용한다.

- 오일러 함수 = 

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

1, 2, 3, 4, 5, 6

- RSA 암호 순서

1 단계 - 충분히 큰 두 소수 P, Q를 찾는다.            (P, Q는 비밀)

2 단계 - 두 소수를 곱하여 n을 만든다.                (N = P * Q)

3 단계 -   

4 단계 - 과 서로소 관계에 있는 수에서 e를 선정

5 단계 -  을 만족하는 d를 구한다.

암호화 - 

복호화 - 

 <- 비밀

 <- 공개