소인수분해 계산기

소인수분해 계산기 소개

이 도구는 2 이상 2¹²⁸ − 1(약 3.4 × 10³⁸, 39자리) 이하의 정수를 소인수분해합니다. 계산은 세 단계입니다. 먼저 2²⁰(약 105만)까지의 작은 소수로 시행 나눗셈을 해서 작은 인수를 떼어 내고, 남은 수가 소수인지 밀러–라빈 판정으로 확인한 뒤, 합성수면 브렌트가 개선한 폴라드 로(ρ) 알고리즘으로 인수 하나를 찾아 재귀적으로 쪼갭니다.

39자리까지 받는 이유는 128비트 정수 연산을 WebAssembly로 직접 구현했기 때문입니다. 자바스크립트의 일반 숫자는 2⁵³(약 9 × 10¹⁵)을 넘으면 정수를 정확히 담지 못합니다. 결과가 나오기까지의 시간은 수의 크기보다 「두 번째로 큰 소인수의 크기」에 달려 있어서, 같은 39자리라도 즉시 끝나기도 하고 몇 시간이 걸리기도 합니다.

시행 나눗셈이 큰 수에서 멈추는 이유

가장 단순한 방법은 2, 3, 5, 7…로 차례로 나눠 보는 것입니다. n이 합성수면 √n 이하의 인수가 반드시 있으므로 √n까지만 나누면 됩니다. 문제는 √n이 너무 크다는 점입니다. 20자리 수라면 √n은 10자리, 즉 최악의 경우 100억 번 가까이 나눠야 하고, 39자리 수라면 10¹⁹번이 넘습니다.

그래서 이 도구는 시행 나눗셈을 2²⁰까지만 씁니다. 대부분의 수는 작은 인수를 여러 개 갖고 있어 이 단계에서 거의 다 쪼개지고, 끝까지 남는 것은 큰 소수이거나 큰 소수 두세 개의 곱뿐입니다.

폴라드 로: √p번 만에 인수 p를 찾는 방법

폴라드 로 알고리즘(1975)은 x → x² + c (mod n) 같은 의사난수 수열을 만들고, 이 수열을 모르는 소인수 p로 나눈 나머지가 언젠가 반복된다는 점을 이용합니다. 생일 문제와 같은 원리로 반복은 대략 √p번 안에 생기고, 그때 두 값의 차와 n의 최대공약수를 구하면 p가 튀어나옵니다. 1980년 브렌트가 순환 검출 방식을 바꿔 속도를 높였고, 같은 해 이 방법으로 페르마 수 F₈(78자리)이 분해되었습니다.

소요 시간이 n이 아니라 가장 작은 소인수 p의 크기에 달려 있다는 점이 핵심입니다. 최악은 두 소인수의 크기가 비슷한 반소수(p ≈ q ≈ √n)로, 이때 반복 횟수는 약 n^(1/4)입니다. 이 도구가 계산 전에 보여 주는 예상 시간도 이 최악을 가정한 값이라, 작은 인수가 하나라도 있으면 실제로는 훨씬 빨리 끝납니다.

직접 재어 보면 차이가 분명합니다. 데스크톱에서 10자리 소수 두 개의 곱(20자리)은 약 0.05초, 13자리 소수 두 개의 곱(25자리)은 약 1.5초가 걸렸습니다. n이 16비트(약 5자리) 커질 때마다 시간이 16배씩 늘어나므로, 20자리 소수 두 개를 곱한 39자리 반소수는 수 시간이 걸릴 수 있습니다. 반면 2¹²⁷ − 1 같은 39자리 소수는 소수 판정만 하면 되므로 0.01초 안에 끝납니다.

소수 판정은 분해보다 훨씬 쉽다

어떤 수가 소수인지 확인하는 일과 그 인수를 찾는 일은 난이도가 전혀 다릅니다. 밀러–라빈 판정은 몇 번의 거듭제곱 나머지 계산만으로 합성수를 가려냅니다. 이 도구는 2⁶⁴ 미만에서는 2부터 37까지의 소수를 밑으로 써서 결정론적으로(틀릴 수 없게) 판정하고, 그보다 큰 수에서는 61까지 18개의 밑을 쓰는 확률적 판정을 합니다. 이 범위에서 18개 밑을 모두 통과하는 합성수는 알려져 있지 않습니다.

페르마 판정만 쓰면 561 = 3 × 11 × 17 같은 카마이클 수에 속습니다. 밀러–라빈은 이런 수도 합성수로 잡아내며, 이 도구에 561을 넣으면 바로 3 × 11 × 17이 나옵니다.

RSA 암호가 소인수분해의 어려움에 기대는 방식

RSA 공개키는 큰 소수 두 개 p, q를 곱한 n을 공개합니다. 암호화는 n만 알면 되지만, 복호화 키를 만들려면 p와 q를 알아야 합니다. 곱하기는 순식간인데 되돌리기는 어렵다는 비대칭이 보안의 근거입니다. 1977년 마틴 가드너의 칼럼에 실린 129자리 수 RSA-129는 1994년에야 전 세계 자원봉사 컴퓨터를 동원해 분해되었습니다.

현재 쓰이는 RSA 키는 보통 2048비트(약 617자리)로, 이 도구의 상한(128비트)과는 차원이 다릅니다. 그런 수에는 폴라드 로가 아니라 수체 체(number field sieve) 같은 훨씬 정교한 알고리즘이 쓰이며, 그래도 공개된 기록은 2048비트에 한참 못 미칩니다. 이 도구로 64비트, 80비트 반소수를 분해해 보면 비트 수가 늘 때 시간이 얼마나 빠르게 커지는지 체감할 수 있습니다.

예시

사용 방법

1. 2 이상의 정수를 입력합니다. 쉼표나 공백은 무시됩니다.
2. 큰 수는 예상 소요 시간이 먼저 표시되고, 계산 중에도 중단할 수 있습니다.
3. 결과는 같은 소인수를 지수로 묶어 보여 주며, 기록을 누르면 등식이 복사됩니다.

자주 묻는 질문