페르마를 이용한 모듈러 역원

덧셈, 뺄셈, 곱셈은 모듈러 아래에서 잘 작동하지만 일반적인 나눗셈은 그렇지 않습니다. 단순히 나눈 다음 나머지를 구할 수는 없습니다. ⚠️

해결 방법은 모듈러 역원입니다. x로 나누는 것을 x의 역원을 곱하는 것으로 바꿀 수 있습니다. 따라서 a / b를 m으로 모듈러 연산한 값은 a에 b의 역원을 곱한 값으로 바뀝니다.

x의 역원은 모듈러 아래에서 x와 곱했을 때 1이 되는 수입니다. 일반적인 산술에서 1/x가 하는 역할을 대신합니다.

x와 m이 공약수를 갖지 않을 때에만 역원이 존재합니다. 1e9+7 같은 소수 모듈러를 사용하면 0이 아닌 모든 x에 역원이 존재합니다.

페르마의 소정리에 따르면 소수 p에 대해 x가 p의 배수가 아니면 x의 p-1제곱은 1과 합동입니다.

x의 인수 하나를 분리하면 나머지는 x의 역원이 되어야 합니다. 따라서 x의 역원은 x를 p-2제곱한 뒤 p로 모듈러 연산한 값입니다.

그 지수는 매우 크므로 이전 수업에서 배운 빠른 거듭제곱을 사용하세요. 파이썬에서는 pow를 한 번 호출하면 전체 계산이 끝납니다.

모듈러 아래에서 a를 b로 나누려면 a에 b의 역원을 곱하세요. 그 나머지가 바로 실제 몫을 p로 모듈러 연산한 값입니다.

어떤 수에 0을 곱해도 1이 될 수 없으므로 0의 역원은 존재하지 않습니다. 모듈러 연산 후 0이 되는 값으로 나누지 않도록 확인하세요.

페르마의 역원 하나를 구하는 일은 빠른 거듭제곱 한 번이므로 O(log p) 시간이 걸립니다. 몇 번의 나눗셈에는 저렴하지만 수백만 번 수행하면 비용이 누적됩니다.

역원이 많이 필요하다면 원소마다 pow를 호출하는 대신 영리한 선형 순회를 사용해 미리 계산하세요. 다음에 배울 nCr에서 이 방법을 활용합니다.

소수 모듈러에서 모듈러 역원을 구하려면 어떤 거듭제곱을 사용하나요?

이제 소수 모듈러에서 모듈러 역원을 곱해 나눗셈을 처리할 수 있습니다. 역원은 pow를 사용해 x의 p-2제곱으로 구합니다. 단, 0의 역원은 절대 구하지 마세요. ✅