해당 글에서는 임의의 소수 p와 p미만의 자연수 n에 대해 n!(mod p)를 빠르게 구하는 방법에 대해 설명하고자 한다. 기본적인 풀이는 반복문으로 O(n)으로 푸는 것이다. 여기서 실제 실행시간에서 n에 곱해지는 상수를 줄일 수도 있고 fft를 이용하여 시간복잡도 O(sqrt(n)log^2(n)) 또는 O(sqrt(n)log(n))으로 구할 수도 있다. 이 글에서는 n에 곱해지는 상수를 줄이는 방법에 대해 설명할 것이다. 하지만 이 글에서 설명하는 방법은 fft를 이용하는 방법에도 적용이 가능하다. 상수를 줄이는 방법은 윌슨의 정리, barrett reduction, SIMD, 르장드르의 정리로 4가지가 있다. 4가지 방법은 모두 동시에 적용시킬 수 있다. 1. 윌슨의 정리윌슨의 정리에 의해 (p-1..