백준 13618: RSA

https://www.acmicpc.net/problem/13618

13618번: RSA

---

 

이 문제는 외국어 문제라서 번역기를 써야 할 텐데,

 

저는 RSA 라는 키워드로 구글링하여 아래 링크를 좀 참고하여 문제를 해결했습니다.

 

( https://yjshin.tistory.com/entry/%EC%95%94%ED%98%B8%ED%95%99-%EB%B9%84%EB%8C%80%EC%B9%AD%ED%82%A4-%EC%95%94%ED%98%B8-RSA-%EC%95%94%ED%98%B8%EC%8B%9C%EC%8A%A4%ED%85%9C )

 

---

 

이 문제에서 주어지는 것은 $N$ 과 $E$ 그리고 $C$ 입니다.

 

그런데 참고 링크에서 다음 식이 주어집니다.

 

$$M = C^{D} \;\; mod \;\; N$$

 

여기서 $D$ 는 다음을 만족하는 값입니다.

 

$$ED = 1 \;\; mod \;\; \phi \left ( N \right )$$

 

그러면 $D$ 를 잘 구해서, $M$ 을 구하면 문제가 해결됨을 알 수 있습니다.

 

---

 

$D$ 는 어떻게 구할 수 있을까요?

 

일단 $D = E^{-1}$ 이라는 걸 생각하면, 페르마의 소정리가 떠오릅니다.

 

하지만 $\phi \left ( N \right )$ 이 소수라는 보장이 없기 때문에, 이를 확장할 필요가 있습니다.

 

Euler's theorem은 정확히 이 상황에 부합합니다. 즉 다음 식을 유도하는데 쓰입니다.

 

$$E^{\phi \left ( \phi \left ( N \right ) \right )} = 1 \;\; mod \;\; \phi \left ( N \right )$$

 

이를 활용하면 손쉽게 $E$ 의 역원을 얻을 수 있습니다.

 

정답 코드는 다음과 같습니다.

 

/*
 * Author : thdtjdals3
 * Date : 2021-12-17
 * Description : BOJ 13618
 * Link : https://www.acmicpc.net/problem/13618
 */

#include <stdio.h>

int PHI (int x);
int power_modular (int A, int X, int M);

int main() {
	
	int N, E, C;
	scanf("%d %d %d", &N, &E, &C);
	
	int D = power_modular(E, PHI(PHI(N)) - 1, PHI(N));

	int answer = power_modular(C, D, N);
	
	printf("%d", answer);
	return 0;
}

int PHI (int x)
{
	int result = x;
	for (int i = 2; i <= x / i; i++)
	{
		if (x % i == 0)
		{
			while (x % i == 0)
			{
				x /= i;
			}
			result -= result / i;
		}
	}
	if (x > 1)
	{
		result -= result / x;
	}
	return result;
}

int power_modular (int A, int X, int M)
{
	int result = 1;
	while(X > 0)
	{
		if (X % 2)
		{
			result = (long long)result * A % M;
		}
		A = (long long)A * A % M;
		X /= 2;
	}
	return result;
}

 

(C11, 0ms, 1116KB, 제출번호 36404722)

---