注意到 p∈{10007,262203414,437367875}。
在 exLucas 算法中需要计算 n!modPQ,其中一个步骤就是要计算 1 到 PQ 中不被 P 整除的数的乘积对 PQ 取模的值,记为 A(P,Q)。
由于 p∈{10007,262203414,437367875},PQ∈{2,3,5,11,397,10007,53,73,1012}。我们可以对这些数预处理 A(P,Q)。将原本 O(PQ) 的计算优化到 O(1),效率显著提升。
实际上,经过计算,对于这些数,A(P,Q)≡−1 (mod PQ),因此连预处理都不用。