어떤 경우에는 어떤 소수 모듈러 p에 대해 복잡한 식을 계산해야 하며, 이러한 식에는 팩토리얼이 포함될 수도 있습니다. 여기서는 모듈러 p가 비교적 작은 경우를 살펴보겠습니다. 이 문제는 팩토리얼이 분수의 분자와 분모 모두에 포함되는 경우에만 의미가 있다는 것은 분명합니다. 실제로 팩토리얼 p!와 그 이후의 모든 팩토리얼은 모듈러 p에서 0이 되지만, 분수에서는 p를 포함하는 모든 인수가 약분될 수 있으며, 그 결과 얻어지는 식은 모듈러 p에서 0이 아닐 수 있습니다.
따라서 문제를 형식적으로 정리하면 다음과 같습니다. 소수 모듈러 p에 대해 n!을 계산해야 하며, 이때 팩토리얼에 포함된 p의 배수인 인수는 모두 고려하지 않습니다. 이러한 팩토리얼을 효율적으로 계산하는 방법을 익히면 다양한 조합 공식(예를 들어, 이항 계수)의 값을 빠르게 계산할 수 있습니다.
알고리즘 이 “수정된” 팩토리얼을 명시적인 형태로 써 봅시다:
n!{%p} = = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdo[…] \cdot (p^2-1) \cdot \underbrace{1}{p^2} \cdot (p[…] = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdo[…] \cdot 1 \cdot 2 \cdot \ldots \cdot (n%p) \pmod p[…]
이렇게 쓰면 “변형된” 팩토리얼이 길이 p인 여러 블록(마지막 블록은 더 짧을 수 있음)으로 나뉘며, 이 블록들은 마지막 원소를 제외하면 모두 같다는 것을 알 수 있습니다:
n!_{%p} = \underbrace{ 1 \cdot 2 \cdot \ldots \c[…] \cdot \underbrace{ 1 \cdot 2 \cdot \ldots \cdot ([…]
블록들의 공통 부분은 쉽게 계산할 수 있습니다. 이는 단순히 (p-1)!\ \rm{mod}\ p이며, 프로그램으로 계산할 수도 있고 윌슨(Wilson)의 정리에 따라 곧바로 (p-1)!\ {\rm mod}\ p = p-1임을 알 수도 있습니다. 모든 블록의 이 공통 부분들을 서로 곱하려면, 구한 값을 p를 법으로 하여 거듭제곱해야 하며, 이는 O(\log n)번의 연산으로 할 수 있습니다(참고: 이진 거듭제곱. 한편, 실제로는 -1을 어떤 지수로 거듭제곱하는 것이므로, 지수의 홀짝성에 따라 결과는 항상 1 또는 p-1 중 하나가 된다는 점에 주목할 수 있습니다. 마지막의 불완전한 블록의 값도 O(p)에 별도로 계산할 수 있습니다. 이제 블록들의 마지막 원소들만 남았으므로, 이들을 더 자세히 살펴봅시다:
n!_{%p} = \underbrace{ \ldots \cdot 1 } \cdot \u[…]
그리고 우리는 다시 “수정된” 팩토리얼에 도달했지만, 이번에는 더 작은 차원입니다(완전한 블록의 개수만큼이며, 그 개수는 \left\lfloor n / p \right\rfloor였습니다). 이렇게 하여 “수정된” 팩토리얼 n!{%p}의 계산을 O(p)번의 연산으로 (n/p)!{%p}의 계산으로 환원하였습니다. 이 점화 관계를 풀어 보면 재귀의 깊이가 O (\log_p n)이 되므로, 알고리즘의 전체 시간 복잡도는 O(p \log_p n)이 됩니다.
구현 구현할 때 재귀를 명시적으로 사용할 필요가 없다는 것은 분명합니다. 꼬리 재귀이므로 반복문으로 쉽게 풀어낼 수 있습니다.
int factmod (int n, int p) { int res = 1; while (n > 1) { res = (res * ((n/p) % 2 ? p-1 : 1)) % p; for (int i=2; i<=n%p; ++i) res = (res * i) % p; n /= p; } return res % p; } 이 구현은 O(p \log_p n)에 동작합니다.