모듈러 거듭제곱 계산기

모듈러 거듭제곱은 정수 밑을 음이 아닌 정수 지수로 거듭제곱한 뒤 양의 모듈러스로 나눈 나머지를 계산합니다. 식 a^b mod m은 0부터 m - 1 사이에서 a^b와 합동인 유일한 나머지를 구합니다. 최종 나머지가 작아도 거듭제곱 값은 매우 빠르게 커지므로 직접 계산은 곧 비현실적이 됩니다. 이 계산기는 거대한 중간 정수를 만들지 않습니다. 이 효율적인 방법을 이진 거듭제곱법, 반복 제곱법 또는 제곱 곱셈법이라고 합니다. 지수를 이진수로 나타내 각 비트를 처리합니다. 먼저 밑을 m으로 나눈 나머지로 줄입니다. 각 단계에서 현재 인수를 제곱한 뒤 m으로 나눈 나머지를 구합니다. 해당 지수 비트가 일이면 그 인수를 결과에 곱하고 즉시 다시 나머지를 구합니다. 모든 중간값을 줄이므로 계산 중 값은 모듈러스의 제곱보다 작게 유지됩니다. 이 알고리즘의 단계 수는 지수의 로그에 비례합니다. 따라서 십억제곱도 십억 번 곱하는 대신 약 삼십 단계의 제곱으로 계산할 수 있습니다. 표시되는 연산 횟수는 제곱과 지수의 일인 비트에 해당하는 선택적 곱셈을 구분합니다. 지수가 영이면 1 mod m을 올바르게 반환합니다. 모듈러 산술에서는 나머지가 같은 수를 동등하게 취급합니다. 예를 들어 17과 5는 12로 나눈 나머지가 모두 5이므로 모듈러스 12에서 합동입니다. 음수 밑도 지원하며 먼저 동등한 음이 아닌 나머지로 정규화합니다. 이 계산기의 지수는 음이 아니어야 합니다. 음의 모듈러 지수를 계산하려면 모듈러 곱셈 역원이 필요하며, 이는 밑과 모듈러스가 서로소일 때만 존재합니다. 모듈러 거듭제곱은 정수론과 현대 암호학의 기초입니다. RSA 암호화와 서명은 메시지를 큰 지수로 거듭제곱한 뒤 합성수로 나눈 나머지를 사용합니다. Diffie-Hellman 키 교환과 많은 이산 로그 시스템은 소수를 모듈러스로 하는 거듭제곱을 사용합니다. 같은 연산은 소수 판별, 의사 난수 생성기, 체크섬, 주기적 패턴, 프로그래밍 대회 문제에도 쓰입니다. 세 입력값은 모두 부동소수점 수가 아닌 정확한 임의 정밀도 정수로 처리됩니다. 따라서 JavaScript의 일반적인 안전 정수 한계를 넘어도 모든 자릿수를 유지합니다. 모듈러스는 일보다 커야 하며 쉼표나 소수점을 입력하면 안 됩니다. 손으로 확인할 때는 먼저 밑의 나머지를 구한 다음 작은 지수에 대해 곱셈을 반복하며 매 단계 나머지를 구하면 좋습니다.