모듈러 거듭제곱 계산기 (aᵇ mod m)

큰 지수에서는 a^b의 자릿수가 천문학적이라 실제로 만들 수 없습니다. 제곱-곱셈은 모든 중간값을 m² 미만으로 유지하므로 지수 크기와 무관하게 빠르고 정확합니다.

a·x ≡ 1 (mod m)을 만족하는 수 x입니다. 밑과 법이 공약수를 갖지 않을 때(gcd = 1)에만 존재하며, 그렇지 않으면 역원이 없다고 표시됩니다. 모듈러 산술에서 '나눗셈'에 쓰이는 값입니다.

a^0 mod m은 임의의 밑에 대해 1입니다(m = 1이면 0). 지수는 음이 아닌 정수여야 하며, 밑은 음수일 수 있고 먼저 0…m−1 범위로 정규화됩니다.

안 된다. 산술 자체는 맞지만, 실제 구현은 상수 시간이기도 해야 한다. 소박한 제곱-곱셈 방식은 지수의 비트에 따라 걸리는 시간이 달라지고, 그 시간 차이로 운영 중인 시스템에서 개인키를 복원한 사례가 있다. 이건 이해하고 결과를 확인하는 데 쓰고, 비밀에 닿는 일에는 검증된 라이브러리를 쓰라.

매 단계마다 m으로 나머지를 취해 숫자가 법의 크기를 넘어 자라지 않게 하고, 반복해서 곱하는 대신 제곱을 쓰기 때문이다. 그러면 1000비트짜리 지수가 천문학적으로 긴 연쇄가 아니라 약 1000번의 제곱이 된다. 지수의 크기가 시간에 대략 선형으로 영향을 주면서, 지수의 값 자체는 비용 어디에도 나타나지 않는 이유가 이것이다.