모듈러 거듭제곱 계산기 (분할 제곱)

지수를 2진수로 쓰고 왼쪽부터 한 비트씩 읽습니다. 비트를 읽을 때마다 결과를 제곱하고, 그 비트가 1이면 밑을 한 번 더 곱합니다. 2진수에서 왼쪽으로 한 칸 미는 것이 지수를 2배 하는 것과 같고 끝에 1을 붙이는 것이 2배 하고 1을 더하는 것과 같아서, 그대로 제곱과 곱하기가 됩니다.

곱셈 횟수가 지수 b가 아니라 log₂b에 비례합니다. RSA가 흔히 쓰는 공개지수 65537은 순진하게 하면 65536번을 곱해야 하지만 2진수로 17비트라 18번이면 끝납니다. 지수가 커질수록 차이가 벌어져, 2¹⁰⁰⁰ 규모에서는 비교 자체가 무의미해집니다.

마지막에 한 번만 나누면 중간값의 자릿수가 감당할 수 없이 커지기 때문입니다. a¹⁰⁰⁰만 해도 자릿수가 수천 개입니다. 곱할 때마다 나머지를 취하면 값이 언제나 n²보다 작게 묶이고, (x mod n)(y mod n) mod n = xy mod n이므로 답은 달라지지 않습니다.

법이 소수 p이고 밑이 p의 배수가 아니면 a^(p−1) ≡ 1 (mod p)이기 때문입니다. 페르마 소정리라고 하며, 이 성질 덕분에 지수를 p−1로 나눈 나머지로 줄여 계산할 수 있습니다. 다만 법이 소수일 때만 성립하므로 아무 때나 쓰면 안 됩니다.

이 도구는 다루지 않습니다. 음수 지수는 곱셈에 대한 역원이 있어야 정의되는데, 모듈러 연산에서는 밑과 법이 서로소일 때만 역원이 존재하기 때문입니다. 역원 자체는 edu/modular-inverse에서 구할 수 있습니다.

전송되지 않습니다. 계산은 전부 브라우저 안에서 이뤄지고, 입력값은 이 브라우저의 localStorage에만 남습니다.