소수성 검사기

소수 검사기는 정수가 소수인지 여부를 알려주며, 대부분의 온라인 계산기와 달리 캐시된 조회 테이블이 아닌 이를 증명한 실제 알고리즘을 보여줍니다. 양수 또는 음수, 작거나 거대한 정수를 입력하면 도구는 크기에 따라 실행할 실제 알고리즘을 결정합니다.

101²(1조) 미만의 숫자에 대해 실제 시험 분할을 실행합니다. 2부터 시작하여 √n의 바닥까지 모든 정수 후보를 가능한 제수로 시도하고 균등하게 나누는 순간(합성)을 중지하거나 최대 √n까지의 모든 후보가 확인된 후(소수) 아무 것도 수행하지 않음을 확인합니다. 후보 수가 많은 경우 표시되는 추적은 처음 시도한 ~18개와 마지막 시도로 제한되며 디스플레이에서 건너뛴 개수에 대한 솔직한 메모와 함께 표시됩니다. 그러나 모든 단일 후보는 여전히 실제로 코드로 확인되며 계산에서는 건너뛰는 항목이 없습니다.

해당 임계값(암호화에 사용되는 크기 범위) 이상인 숫자의 경우 시험 분할에 너무 오랜 시간이 걸리므로 도구는 13개의 주요 증인(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41)으로 구성된 고정된 결정론적 세트를 사용하여 밀러-라빈 소수성 테스트로 전환합니다. 이 정확한 증인 세트는 잘 알려진 결과입니다. 계산 검증에 의해 설정된 경계인 3,317,044,064,679,887,385,961,981(약 3.3×10²⁴) 미만의 모든 n에 대해 거짓 긍정이 없습니다(Sorenson & Webster, 2015 및 이것이 속한 널리 재현된 결정론적 증인 테이블 참조). 그 이상에서는 동일한 테스트가 계속 실행되지만 도구는 보장이 수학적 확실성보다는 매우 강력한 확률적 보증이 된다는 것을 솔직하게 알려줍니다.

Miller-Rabin 추적은 d 홀수로 n − 1 = 2ˢ × d를 기록한 다음 실제 BigInt 모듈러 지수(제곱 및 곱셈, 모든 단일 단계에서 모듈로 n을 줄여 숫자가 폭발하지 않도록)를 단계별로 첫 번째 증인에 대해 보고하고, 숫자가 소수가 아닌 것으로 판명되면 합성성을 증명하는 증인을 포함하여 각 증인의 평결을 보고합니다. 모든 것이 브라우저에서 로컬로 실행됩니다. 서버도 없고, 외부 API도 없으며, 어떤 데이터도 기기 밖으로 나가지 않습니다.