[C++] 소인수분해: 두 소수 p, q의 곱 n이 주어질 때, p, q 알아내기

이 사람은 왜 이런 짓을 했는가?

시험 기간인데 시험 공부는 하기 싫어서 간단한 알고리즘을 짜봤다.

문제

RSA 알고리즘을 배울 때 꼭 한 번씩 들어보는 말.

두 소수 p, q가 주어졌을 때 n을 계산하는 건 매우 단순한 일이지만, 두 소수의 곱 n이 주어졌을 때 p, q를 알아내는 건 NP 문제다.

그래서 어떻게 하면 n이 주어졌을 때 p, q를 빠르게 알아낼 수 있을까?라는 질문이 샤워 도중 떠올랐고, 샤워하면서 한 생각을 코드로 옮겨봤다.

알고리즘

거창한 문제에 비해 내 생각은 단순했다. twosum 문제를 좀 응용하면 되지 않을까?

정확한 사고 과정은 아래와 같았다.

두 소수 p, q를 곱한 n이 있다면, p와 q는 sqrt(n)에서 비슷하게 떨어져 있지 않을까?
- 3 * 13, 7 * 13을 해봄, 규칙성은 찾지 못함. (대강 1/3쯤 sqrt(n)이 위치한다는 건 찾음)
twosum 알고리즘을 사용하면, 정렬된 배열에서 합이 n이 되는 두 수를 O(n)에 찾을 수 있다.
같은 원리로 두 수의 곱도 찾을 수 있지 않을까?
그럼 sqrt(n)부터 두 소수의 곱도 찾을 수 있겠네?
소수 테이블만 있으면 풀 수 있는 거 아냐?

그래서 해봤더니 됐다.

물론 twosum은 양 끝에서 시작해 서서히 조여오지만, 소수 테이블의 크기가 큰 편이므로 (사실 그렇게 크진 않다. 100만 보다 작은 소수가 고작 78498개니까.) 이 경우 어려울 것 같았다.

그래서 n에서 p, q를 찾는 건 반대로 n의 루트(sqrt(n))에서 시작, 서서히 양 끝으로 이동하는 방식을 썼다.

다만 몇 가지 제한 사항을 걸어두고 알고리즘을 작성했는데,

소수 테이블은 이미 작성되어 있다.
p, q는 1,000 이하의 소수다.
1. 이것도 소수 테이블을 작성하는 프로그램을 짜면 범위는 무한정 늘릴 수 있다.
  다만 이번엔 내가 손으로 따라쳐서... 1,000 이하의 소수만 사용했다.
입력은 반드시 1,000 이하인 두 소수의 곱만 들어온다.
1. 사실 예외 처리하면 쉽게 처리되긴 하는데, 귀찮아서...

그렇게 작성한 코드는 아래와 같다.

코드

// 두 소수 p, q의 곱 N이 있을 때, 두 소수 p, q를 찾는 알고리즘
// 소수 목록을 vector로 저장해두고, twosum을 응용해 O(n) 안에 푼다.


#include <iostream>
#include <vector>

// 1,000 이하 모든 소수를 오름차순으로 작성했다.
std::vector<int> prime = {
	2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
	31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
	73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
	127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
	179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
	233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
	283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
	353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
	419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
	467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
	547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
	607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
	661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
	739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
	811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
	877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
	947, 953, 967, 971, 977, 983, 991, 997
};

// 이진 탐색 사용, n보다 작은 가장 큰 소수의 인덱스를 반환한다.
int GetFloorPrimeIndex(int n) {
	int i = 0, j = prime.size();

	while ((j - i) > 1) {
		int k = (i + j) / 2;
		if (prime[k] == n) {
			return k;
		}

		else if (prime[k] < n) {
			i = k;
		}

		else {
			j = k - 1;
		}
	}

	if (prime[j] <= n) {
		return j;
	}

	else if (prime[i] <= n) {
		return i;
	}

	else {
		return -1;
	}
}

// n은 항상 두 소수의 곱이라고 가정
std::pair<int, int> PrimeFactorization(int n) {
	// O(1)인 특수 케이스 -> 아마 보안상 안 쓰지 않을까?
	if (n % 2 == 0) {
		return std::make_pair(2, n / 2);
	}

	int k = (int)std::sqrt(n);

	int i, j;
	i = j = GetFloorPrimeIndex(k);
	
	// twosum 응용
	while (true) {
		int mult = prime[i] * prime[j];

		if (mult == n) {
			return std::make_pair(prime[i], prime[j]);
		}

		else if (mult < n) {
			j++;
		}

		else {
			i--;
		}
	}

	// 입력 값을 제한했기에 이 리턴엔 도달하지 않는다.
	return std::make_pair(-1, -1);
}

int main() {
	//// n을 바로 입력받는 경우
	//int n = 0;
	//std::cin >> n;
	//
	//std::pair<int, int> answer = PrimeFactorization(n);
	// 
	//std::cout << answer.first << ", " << answer.second;

	// 두 소수를 바로 입력받는 경우(테스트가 편함)
	int a, b;
	std::cin >> a >> b;

	std::pair<int, int> answer = PrimeFactorization(a * b);

	std::cout << a * b << '\n';
	std::cout << answer.first << ", " << answer.second;
}

크게 2가지 함수를 사용한다.

int GetFloorPrimeIndex(int n)
- n보다 작은 소수 중, 최댓값의 인덱스를 반환한다.
- 예를 들어 9가 입력되면, 9보다 작은 가장 큰 소수는 7이다. prime 벡터에서 7의 인덱스는 3이므로, 3을 반환한다.
std::pair<int, int> PrimeFactorization(int n)
- n을 두 소수 p, q로 분리한다.
- 시작 인덱스는 GetFloorPrimeIndex에 sqrt(n)을 집어넣는다. 적당한 중간 값에서 시작할 수 있다.
- while의 조건으로 true를 넣어둔 건, 입력 값 n이 항상 두 소수 p, q로 나눠진다는 조건 때문이다.
  n이 다른 값인 경우도 고려하고 싶다면 i >= 0으로 넣으면 된다.

main 함수에서 입력을 받는데, 쉬운 테스트를 위해 두 소수 a, b를 입력받는 걸 살려뒀다.

예를 들어 673, 977을 입력하면 두 수의 곱인 657,521이 들어가고, 이걸 풀어서 673, 977을 출력한다.

원한다면 주석으로 처리해둔 것처럼 n을 직접 입력하면 된다.

돌려보면 아래 사진처럼 나온다.

시간복잡도는?

우선 PrimeFactorization 함수에 진입한 후, GetFloorPrimeIndex 함수를 호출한다.

GetFloorPrimeIndex 함수는 이진 탐색 알고리즘을 사용하므로, 시간복잡도는 O(log n).

이때 n은 벡터의 크기인 168이다. (최악의 경우 8번 반복)

이제 while문에 접근. 하지만 sqrt(n) (대충 어딘가 한 곳)에서 시작해 i는 왼쪽으로, j는 오른쪽으로 이동하는 twosum 알고리즘을 응용했으니, 시간복잡도는 O(n)이다.

이때 n은 역시나 벡터의 크기인 168이다.

그러니 정리하면 O(log n) + O(n) = O(n)이고, 이때 n은 소수 벡터의 크기다.

100만 이하 소수의 개수가 78,498개이므로, 어림잡아 1,000,000 * 1,000,000, 즉 1조 이하의 수라면 연산량은 많아봐야 80,000보다 작다. 이정도면 충분히 효율적인 거 아닐까?

나는 소수 테이블을 1,000 이하의 소수만 작성했기에 994,009 이하의 n에 대해서만 작동한다. 하지만 에라토스테네스의 체를 이용해 소수 테이블만 작성할 수 있다면, 작성에 얼마나 오랜 시간이 걸리든 해내기만 한다면, 더 큰 수도 소인수분해하는 게 어렵진 않을 것이다.

그럼 이제 은행 털 수 있나요?

그럴 리가. 적어도 내가 알기론 RSA 알고리즘을 무력화하지 못하는 건, 이 보안 시스템에 쓰이는 소수 p, q가 매우 큰 자리의 수기 때문이다. 100만 자리랬나? 참고로 1조는 13자리다.

애초에 정수 연산 자체가 불가능할 정도니, 딱히 의미는 없을 것 같다.

하지만 재밌으면 된 거 아닐까?

근데 이게 얼마나 효율적인 건가요?

기존 소인수분해 알고리즘 중 가장 단순한 방법은, 2 이하의 모든 수로 나눠보는 것이다.

이때 일반적으로 sqrt(n)까지만 나눠보므로, 예를 들어 100만 언저리의 n을 입력했다면 최악의 경우 997번의 나눗셈 연산이 실행된다.

하지만 위 알고리즘을 적용하면, 100만 언저리의 n은 168개의 소수만 검사해보면 된다.

**근데 3 * 7919는 기존 방식이 더 빠르지 않나요? 심지어 계산 못 하는데?**

어라

+)

근데 어차피 소수 테이블을 만들거면, 그냥 테이블 내 모든 소수로 나눠보는 게 훨씬 빠르고(O(N^1/2)) 넓은 범위를 커버한다. 즉 다운그레이드

참고 문헌

위키백과, “소수 목록”, https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_%EB%AA%A9%EB%A1%9D
ChatGPT 3.5, "100만 이하 소수의 개수는 몇 개야?"

'삽질의 기록' 카테고리의 다른 글

[Unity] UI Text 가비지 제거, 삽질의 기록 (0)	2023.02.13

가을의 개발 일지

[C++] 소인수분해: 두 소수 p, q의 곱 n이 주어질 때, p, q 알아내기

이 사람은 왜 이런 짓을 했는가?

문제

알고리즘

코드

시간복잡도는?

그럼 이제 은행 털 수 있나요?

근데 이게 얼마나 효율적인 건가요?

**근데 3 * 7919는 기존 방식이 더 빠르지 않나요? 심지어 계산 못 하는데?**

+)

참고 문헌

'삽질의 기록' 카테고리의 다른 글

티스토리툴바

[C++] 소인수분해: 두 소수 p, q의 곱 n이 주어질 때, p, q 알아내기

이 사람은 왜 이런 짓을 했는가?

문제

알고리즘

코드

시간복잡도는?

그럼 이제 은행 털 수 있나요?

근데 이게 얼마나 효율적인 건가요?

근데 3 * 7919는 기존 방식이 더 빠르지 않나요? 심지어 계산 못 하는데?

+)

참고 문헌

'삽질의 기록' 카테고리의 다른 글

'삽질의 기록' Related Articles

티스토리툴바

**근데 3 * 7919는 기존 방식이 더 빠르지 않나요? 심지어 계산 못 하는데?**