소인수분해

Prime Factorization; Integer Factorization

하나의 정수를 소수의 곱으로 나누어 나타내는 것

• 어떤 정수를 소인수(소수인 약수)들의 곱으로 분해하는 것이다.
• 1보다 큰 모든 정수는 소수의 곱으로 유일하게 나타낼 수 있다(산술의 기본 정리).
• 예 : 143 = 11 × 13, 360 = 2³ × 3² × 5

한 방향으로만 쉽다

충분히 큰 두 개의 소수를 곱하는 것은 쉽지만, 그 곱을 다시 소인수분해하는 것은 매우 어렵다. 곱셈은 자릿수에 대해 거의 비례하는 시간이면 되는데, 소인수분해는 알려진 어떤 방법도 자릿수에 대해 다항 시간이 아니다.

이 비대칭이 공개키 암호의 바탕이 된다. 두 소수 p, q 는 개인키로 숨기고 n = pq 만 공개해도 n 에서 p, q 를 알아낼 수 없다.

이 문제에 기반한 암호

• RSA 암호화 : n = pq 를 공개한다. n 을 소인수분해할 수 있으면 개인키를 구할 수 있다
• 라빈 암호 : 합성수 법에서 제곱근을 구하는 문제가 소인수분해와 같은 난이도라는 성질을 쓴다
• 골드바서-미칼리 : 이차 잉여 판정의 어려움을 쓰며, 이것도 소인수를 알면 쉬워진다

이산대수 문제에 기반한 엘가말·디피-헬먼 키 교환·타원 곡선 암호 와는 바탕이 되는 문제가 다르다.

알려진 방법

• 시행 나눗셈 : √n 까지 나눠 본다. 작은 수에만 쓸 수 있다
• 폴라드 rho, p−1 방법 : 특수한 형태의 수에 빠르다
• 이차 체, 일반 수체 체(GNFS) : 현재 가장 빠른 일반 방법이다
• 쇼어 알고리즘 : 양자 컴퓨터에서는 다항 시간에 풀린다. RSA 가 양자 컴퓨터에 취약한 이유다

그래서 키 길이를 늘려 대응해 왔다. 지금은 RSA 2048비트 이상을 쓴다.

같이 보기

• RSA 암호화
• 공개키 암호화
• 암호 알고리즘 보안강도