numbers 소인수분해 계산기 star

작동 방식

소인수분해란 어떤 수를 그것을 이루는 소수 단위의 곱으로 나타내는 것을 말합니다 — 예를 들어 60 = 2² × 3 × 5입니다. 산술의 기본 정리는 1보다 큰 모든 정수가 (인수의 순서를 바꾸는 것을 제외하면) 정확히 하나의 그러한 분해를 갖는다는 것을 보장합니다: 60을 소인수로 분해하는 방법은 어떤 순서로 나누어보든 오직 하나뿐입니다. 이 유일성이야말로 소인수분해를 임의의 선택 문제가 아니라 의미 있고 명확하게 정의된 연산으로 만들어 줍니다.

이 도구는 시험 나눗셈으로 소인수분해를 찾습니다: 먼저 2로 나눌 수 있는 만큼 모두 나누고(정확히 몇 번 나누어떨어지는지 셉니다), 그다음 3, 5, 7, 9, 11…과 같은 홀수 후보로 넘어가 남은 수의 제곱근까지 각각을 나누어떨어지는 만큼 나눕니다. 360의 계산 과정 예시: 2로 세 번 나누어(360→180→90→45, 즉 2³), 45는 홀수이므로 3으로 두 번 나누고(45→15→5, 즉 3²), 남은 5는 그 자체로 소수입니다(5¹). 결과: 360 = 2³ × 3² × 5이며, 이를 다시 곱해 보면 — 8 × 9 × 5 — 360임이 확인됩니다. 남은 수의 제곱근까지 어떤 후보로도 나누어떨어지지 않으면, 그 남은 수 자체가 소수이며 그것으로 소인수분해가 마무리됩니다.

알아두어야 할 점

작거나 중간 크기의 수는 이 방식으로 거의 즉시 인수분해됩니다. 하지만 자릿수가 수백 자리에 달하는 매우 큰 수에서는 같은 시험 나눗셈 방식이 계산상 매우 어려워집니다 — 확인해야 할 후보의 수가 엄청나게 늘어나며, 일반적인 정수에 대해 고전 컴퓨터에서 효율적인(다항 시간) 알고리즘이 알려져 있지 않기 때문입니다. 이러한 비대칭성 — 두 개의 큰 소수를 곱하는 것은 빠르지만, 그 곱을 다시 소인수로 분해하는 것은 느리다는 점 — 은 단순한 흥미거리가 아니라 RSA 공개키 암호화의 정확한 보안 기반입니다: 공개키는 두 개의 거대한 비밀 소수의 곱으로 만들어지며, 암호를 깨려면 그 곱을 소인수분해해야 하는데, 현재 사용되는 키 크기에서는 이것이 사실상 불가능합니다.

• 1은 소인수분해가 전혀 존재하지 않습니다 — 소수도 합성수도 아니며, "공집합의 곱" 관례에 따라 특별한 경우로 취급됩니다.
• 어떤 수가 자기 자신의 제곱근까지 시험 나눗셈을 거치고도 아무것도 나누어떨어지지 않는다면, 정의상 그 수는 소수입니다.
• 암호화를 넘어, 소인수분해는 분수를 약분하고, 최대공약수(GCD)와 최소공배수(LCM)를 구하고, 어떤 수의 약수 개수를 알아내는 데에도 기초가 됩니다.