소수 판별기（무료）— 최대 1,000자리·소인수분해까지

여담 ― 소수는 왜 중요한가

소수는 흔히 "수의 원자"라고 불립니다. 산술의 기본정리에 따르면 1보다 큰 모든 정수는 소수의 곱으로 오직 한 가지 방법으로만 나타낼 수 있습니다. 즉 소수는 모든 정수를 조립하기 위한, 더 이상 쪼갤 수 없는 부품인 셈입니다. 위에 표시되는 소인수분해가 유일한 이유도 여기에 있으며, 360은 2³ × 3² × 5이고 그 밖의 표현 방법은 없습니다.

거대한 수가 소수인지 "판별하는" 것과 그것을 "소인수분해하는" 것은 서로 다른 문제이며, 그 차이의 역사는 알아둘 만합니다. 페르마의 소정리를 쓰면 빠른 판별이 가능하지만, 어떤 밑을 사용해도 통과해 버리는 합성수가 존재합니다. 그중 가장 작은 예가 561이며 위의 버튼으로 확인해 볼 수 있습니다（이런 수를 카마이클 수라고 합니다）. 밀러-라빈 판정법은 도중에 1의 제곱근을 확인함으로써 이 빈틈을 막았고, 처음 13개의 소수를 밑으로 사용하면 약 3.3 × 10²⁴ 미만의 모든 수에 대해 결정적인 판정법이 됨이 증명되어 있습니다. 그 범위를 넘어서면 이 페이지는 강한 뤼카 판정법을 더한 Baillie–PSW 판정법을 사용합니다. 이 판정을 통과하는 합성수는 아직 하나도 발견되지 않았지만 증명은 없기 때문에, 매우 큰 수의 결과는 "확률적 소수"로 표시합니다.

이처럼 "판별은 쉬운데 분해는 어렵다"는 비대칭성이 현대 암호 기술을 떠받치고 있습니다. HTTPS 통신과 전자서명을 지금도 지켜 주는 RSA 암호는 큰 소수 두 개를 곱해서 공개키를 만듭니다. 그 곱에서 원래의 소수를 되찾는 일은 사실상 불가능하다고 여겨지기 때문에, 검증은 순식간에 끝나지만 분해는 할 수 없는 상태를 만들 수 있는 것입니다. 이 페이지에서도 그 차이를 체감할 수 있습니다. 1,000자리 수의 소수 판별은 거의 즉시 끝나지만, 30자리 소수 두 개를 곱한 60자리 합성수는 소인수분해를 끝내지 못합니다.

소수에는 수학에서 가장 오래된 미해결 문제도 남아 있습니다. 11과 13, 또는 1,000,000,000,061과 1,000,000,000,063 같은 쌍둥이 소수가 무한히 존재하는지는 아직 아무도 모릅니다. 소수 자체가 무한하다는 사실은 기원전 300년경 유클리드가 이미 증명했는데도 말입니다. 기록 갱신을 위한 탐색도 계속되고 있습니다. GIMPS 프로젝트의 참가자들은 2^p − 1 형태의 메르센 수를 나누어 조사하고 있으며, 현재 알려진 가장 큰 소수는 2024년에 발견된 2¹³⁶²⁷⁹⁸⁴¹ − 1로 41,024,320자리에 이릅니다.