페르마 소정리 계산기

페르마 소정리는 소수, 거듭제곱, 모듈러 산술을 연결합니다. 표준형에 따르면 p가 소수이고 a가 p로 나누어떨어지지 않으면 a^(p - 1)을 p로 나눈 나머지는 1입니다. 합동식으로는 a^(p - 1)이 법 p에서 1과 합동입니다. a = 2, p = 7이면 2^6 = 64이고, 64를 7로 나눈 나머지는 1입니다. 동치인 형태는 p가 소수일 때 모든 정수 a에 대해 a^p가 법 p에서 a와 합동이라고 말합니다. 이 형태는 p가 a를 나누어떨어지게 하는 경우도 포함하며, 그때는 양쪽 나머지가 모두 영입니다. 표준형은 a와 p의 최대공약수가 1이어야 합니다. 계산기는 소수 여부와 서로소 조건을 확인한 뒤 선택한 합동식을 계산합니다. 큰 거듭제곱을 직접 계산하면 중간값이 엄청나게 커질 수 있습니다. 대신 이 도구는 반복 제곱법이라고도 하는 이진 모듈러 거듭제곱을 사용합니다. 현재 밑을 반복해서 제곱하고 곱셈할 때마다 p로 나눈 나머지를 취합니다. 정확한 나머지를 유지하면서 다루기 어려운 전체 거듭제곱 값을 피하고, 지수에 대해 로그 수준의 단계만 필요합니다. 실용적인 암호 소프트웨어의 핵심 방법입니다. 이 정리로 어떤 수가 합성수임을 증명할 수 있습니다. 서로소인 밑에서 합동식이 성립하지 않으면 후보 모듈러스는 소수일 수 없습니다. 그러나 페르마 검사를 한 번 통과했다고 소수로 증명되는 것은 아닙니다. 일부 합성수는 특정 밑에서 통과하며, 카마이클 수는 자신과 서로소인 모든 밑에서 표준 검사를 통과합니다. 따라서 신뢰할 수 있는 소수 판정에는 더 강한 결정적 검사나 신중하게 밑을 선택한 Miller-Rabin 같은 검사가 필요합니다. 페르마의 결과는 정수론과 컴퓨팅의 여러 분야에 쓰입니다. 모듈러 계산의 지수를 줄이고, 소수 판정의 아이디어를 제공하며, 공개 키 암호의 수학적 기반에 기여합니다. RSA는 관련된 오일러 정리에 더 직접적으로 의존하지만 페르마 소정리는 그 핵심에 있는 소수 모듈러스의 성질을 설명합니다. p가 소수이고 a가 법 p에서 영이 아니면 a^(p - 2)를 법 p로 계산해 모듈러 역원도 구할 수 있습니다. 이 계산기는 수업 예제를 검증하고 모듈러 규칙을 탐구하는 데 사용하고, 큰 암호용 소수를 인증하는 데 사용하지 마세요. 신뢰할 수 있는 소수 판정을 위해 입력은 JavaScript 안전한 정수로 제한되며, 거듭제곱 자체는 정확한 정수 연산을 사용합니다. 성공 결과는 선택한 소수와 밑이 지정한 정리 형태를 만족함을 확인할 뿐, 검사하지 않은 합성수 후보가 소수임을 그 자체로 증명하지는 않습니다.