소수 검사기

이 소수 검사기는 어떤 정수가 소수인지 알려줄 뿐만 아니라, 대부분의 온라인 계산기와 달리 결과를 증명한 실제 알고리즘 과정을 보여줍니다. 미리 저장된 조회 테이블이 아닙니다. 양수, 음수, 작은 수, 아주 큰 수 무엇이든 입력하면, 이 도구는 크기에 따라 자동으로 적합한 실제 알고리즘을 선택합니다.

10¹²(1조) 미만의 수에는 실제 시험 나눗셈을 수행합니다. 2부터 시작하여 √n의 정수 부분까지 가능한 모든 정수 후보 약수를 시도하고, 나누어떨어지는 약수가 발견되면 즉시 멈추거나(합성수), √n까지의 모든 후보를 확인한 후 나누어떨어지는 약수가 없음을 확인하면(소수) 판정합니다. 후보 약수의 개수가 너무 많을 경우, 표시되는 추적 정보는 처음 약 18개와 마지막 하나로 제한되며 몇 개가 생략되었는지 솔직하게 표시합니다. 하지만 코드에서는 모든 후보 약수를 실제로 전부 확인하며, 연산 과정에서는 어떤 약수도 건너뛰지 않습니다.

암호학에서 사용되는 크기 이상의 수에는 시험 나눗셈에 시간이 너무 오래 걸리므로, 고정된 13개의 소수 검증자(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41)를 사용하는 Miller–Rabin 소수 판별법으로 전환합니다. 이 정확한 검증자 집합은 잘 알려진 결과로, 3,317,044,064,679,887,385,961,981(약 3.3×10²⁴) 미만의 모든 n에 대해 오탐지가 없음이 계산적으로 검증되었습니다(Sorenson & Webster, 2015 및 이에 속한 널리 재현된 결정론적 검증자 표 참조). 이 경계를 넘는 수에 대해서도 동일한 테스트가 실행되지만, 수학적 확정성이 아닌 극도로 강력한 확률적 보장임을 솔직하게 알려줍니다.

Miller–Rabin 추적 과정은 n − 1 = 2ˢ × d(d는 홀수)로 분해한 후, 실제 BigInt 모듈러 지수 연산(제곱 후 곱하기, 매 단계마다 n으로 나눈 나머지를 구해 숫자가 폭발적으로 커지지 않게 함)을 첫 번째 검증자에 대해 비트 단위로 보여줍니다. 또한 각 검증자의 판정 결과와, 수가 소수가 아닌 것으로 판명될 경우 합성수임을 증명하는 데 사용된 검증자를 보고합니다. 모든 과정은 브라우저 내에서 로컬로 실행되며, 서버, 외부 API, 사용자 기기 외부로의 데이터 전송은 전혀 없습니다.