두 가지 예시: 소인수분해와 GCD

오늘날 존재하는 고전 컴퓨터는 엄청나게 빠르며, 그 속도는 계속해서 증가하고 있는 것처럼 보입니다. 이러한 이유로 일부 사람들은 컴퓨터가 너무 빠르기 때문에 어떤 계산 문제도 그 범위를 벗어나지 않는다고 믿고 싶어할 수 있습니다.

이러한 믿음은 잘못된 것입니다. 어떤 계산 문제들은 본질적으로 너무나 복잡하여, 비록 이를 해결하는 알고리즘이 존재한다 하더라도, 오늘날 지구상의 어떤 컴퓨터도 적당한 크기의 입력에 대해서조차 인간의 수명 내에 — 심지어 지구 자체의 수명 내에 — 이러한 알고리즘을 끝까지 실행할 만큼 빠르지 않습니다.

더 자세히 설명하기 위해, 정수 소인수분해 문제를 소개하겠습니다.

정수 소인수분해

입력: 정수 $N\geq 2$
출력: $N$ 의 소인수분해

$N$ 의 소인수분해란 $N$ 의 소인수 목록과 곱셈을 통해 $N$ 을 얻기 위해 거듭제곱해야 하는 지수들을 의미합니다. 예를 들어, $12$ 의 소인수는 $2$ 와 $3$ 이며, $12$ 를 얻기 위해서는 $2$ 의 $2$ 제곱과 $3$ 의 $1$ 제곱의 곱을 구해야 합니다.

12 = 2^2 \cdot 3

소인수의 순서를 제외하면, 각 양의 정수 $N\geq 2$ 에 대해 소인수분해는 단 하나만 존재하는데, 이는 산술의 기본 정리로 알려진 사실입니다.

Python으로 작성한 몇 가지 간단한 코드 예제가 정수 소인수분해와 이 논의와 관련된 다른 개념들을 설명하는 데 도움이 될 것입니다. 다음 임포트가 이러한 예제에 필요합니다.

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"sympy": "sympy"}
_missing = [pip for module, pip in _needed.items()
            if importlib.util.find_spec(module) is None]
# One at a time, so a package that fails to install does not block the others
for _pip in _missing:
    %pip install -q {_pip}
if not _missing:
    print("\u2713 All required packages are installed")

import math
from sympy.ntheory import factorint

Python용 SymPy 기호 수학 패키지의 factorint 함수는 우리가 선택하는 어떠한 입력 $N$ 에 대해서도 정수 소인수분해 문제를 해결합니다. 예를 들어, 12에 대한 소인수분해를 얻을 수 있으며, 이는 자연스럽게 위의 분해와 일치합니다.

N = 12
print(factorint(N))

{2: 2, 3: 1}

$12$ 와 같은 작은 숫자를 소인수분해하는 것은 쉽지만, 소인수분해할 숫자 $N$ 이 커지면 문제는 더 어려워집니다. 예를 들어, 훨씬 큰 숫자에 대해 factorint를 실행하면 일반적인 개인용 컴퓨터에서 짧지만 눈에 띄는 지연이 발생합니다.

N = 3402823669209384634633740743176823109843098343
print(factorint(N))

{3: 2, 74519450661011221: 1, 5073729280707932631243580787: 1}

$N$ 의 값이 훨씬 더 크면, 적어도 우리가 아는 한 문제는 불가능할 정도로 어려워집니다. 예를 들어, 1991년부터 2007년까지 RSA Laboratories가 운영한 RSA Factoring Challenge는 다음 숫자를 소인수분해하는 데 10만 달러의 상금을 제시했으며, 이 숫자는 309자리의 십진수(또는 이진수로 쓰면 1024비트)입니다. 이 숫자에 대한 상금은 결국 수령되지 못했고, 그 소인수들은 여전히 알려지지 않았습니다.

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

RSA1024에 대해 factorint를 실행할 필요는 없습니다. 우리 생애 내에는 끝나지 않을 것입니다.

큰 정수를 소인수분해하는 알고리즘 중 알려진 가장 빠른 것은 *수체 체(number field sieve)*로 알려져 있습니다. 이 알고리즘 사용의 예로, 250자리의 십진수(또는 이진수로 쓰면 829비트)를 가진 RSA challenge 번호 RSA250이 2020년에 수체 체를 사용하여 소인수분해되었습니다. 이 계산에는 전 세계 수만 대의 기계에 분산된 수천 CPU 코어-년이 필요했습니다. 여기서 해답을 확인함으로써 이러한 노력을 감상할 수 있습니다.

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)

True

RSA 공개키 암호 시스템의 보안은 정수 소인수분해의 계산적 어려움에 기반하고 있으며, 정수 소인수분해에 대한 효율적인 알고리즘이 있다면 이를 깨뜨릴 수 있다는 의미입니다.

다음으로는 관련이 있지만 매우 다른 문제, 즉 두 정수의 최대공약수(또는 GCD)를 계산하는 문제를 고려해 보겠습니다.

최대공약수 (GCD)

입력: 음이 아닌 정수 $N$ 과 $M$ , 그 중 적어도 하나는 양수
출력 $:N$ 과 $M$ 의 최대공약수

두 숫자의 최대공약수는 둘 다 나누어떨어지게 하는 가장 큰 정수입니다.

이 문제는 컴퓨터로 해결하기 쉽습니다 — 두 입력 숫자를 서로 곱하는 것과 거의 같은 계산 비용이 듭니다. Python math 모듈의 gcd 함수는 RSA1024보다 훨씬 큰 숫자의 최대공약수를 눈 깜짝할 사이에 계산합니다. (실제로 이 예제의 두 숫자의 GCD는 RSA1024입니다.)

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

이것이 가능한 이유는 GCD를 계산하기 위한 매우 효율적인 알고리즘이 있기 때문이며, 그 중 가장 잘 알려진 것이 2,000년도 더 전에 발견된 유클리드 알고리즘입니다.

우리가 아직 발견하지 못한, 정수 소인수분해를 위한 빠른 알고리즘이 존재해서 RSA1024와 같은 큰 숫자들을 눈 깜짝할 사이에 소인수분해할 수 있게 될 가능성이 있을까요? 답은 "그렇다"입니다. 비록 GCD를 계산하기 위한 유클리드 알고리즘만큼 단순하고 우아한 소인수분해를 위한 효율적인 알고리즘이 지금쯤은 발견되었어야 한다고 기대할 수 있지만, 우리가 지금까지 하나를 찾지 못했다는 사실 외에는 정수 소인수분해를 위한 매우 빠른 고전 알고리즘의 존재를 배제할 만한 것은 아무것도 없습니다. 내일이라도 하나가 발견될 수 있습니다 — 하지만 너무 기대하지는 마세요. 여러 세대의 수학자들과 컴퓨터 과학자들이 찾아왔고, RSA1024와 같은 숫자의 소인수분해는 여전히 우리의 손이 닿지 않는 곳에 있습니다.