基本上问题归结为计算a^T mod m对于给定的a, m和一个术语T那是大得离谱。然而，我们可以评估T mod n给定模数n比T。所以我们问：“是否有一个整数n，使得a^(T mod n) mod m = a^T mod m?"
Now if a and m是互质的，我们知道n = phi(m)满足我们的条件欧拉定理:
a^T (mod m)
= a^((T mod phi(m)) + k * phi(m)) (mod m) (for some k)
= a^(T mod phi(m)) * a^(k * phi(m)) (mod m)
= a^(T mod phi(m)) * (a^phi(m))^k (mod m)
= a^(T mod phi(m)) * 1^k (mod m)
= a^(T mod phi(m)) (mod m)
如果我们可以计算phi(m)（这很容易做到，例如O(m^(1/2))或者如果我们知道素因数分解m），我们将问题简化为计算T mod phi(m)和一个简单的模幂.
What if a and m不是互质的吗？情况并不像以前那么愉快，因为可能没有有效的n与财产a^T mod m = a^(T mod n) mod m对全部T。然而，我们可以证明序列a^k mod m for k = 0, 1, 2, ...在某个点之后进入循环，即存在x and C with x, C < m，使得a^y = a^(y + C)对全部y >= x.
Example: For a = 2, m = 12，我们得到序列2^0, 2^1, ... = 1, 2, 4, 8, 4, 8, ... (mod 12)。我们可以看到带参数的循环x = 2 and C = 2.
我们可以通过暴力计算序列元素来找到循环长度a^0, a^1, ...直到找到两个索引X < Y with a^X = a^Y。现在我们设置x = X and C = Y - X。这给了我们一个算法O(m)每次递归求幂。
如果我们想做得更好怎么办？谢谢于尔基·拉赫托宁来自 Math Exchange 提供以下算法的要点!
让我们评估一下序列d_k = gcd(a^k, m)直到我们找到一个x with d_x = d_{x+1}。这最多需要log(m)GCD 计算，因为x受质因数分解中最高指数的限制m. Let C = phi(m / d_x). 我们现在可以证明 a^{k + C} = a^k对全部k >= x，所以我们找到了循环参数O(m^(1/2)) time.
假设我们已经找到了x and C并想要计算a^T mod m现在。
如果T < x，通过简单的模幂运算来执行该任务是微不足道的。否则，我们有T >= x因此可以利用循环：
a^T (mod m)
= a^(x + ((T - x) mod C)) (mod m)
= a^(x + (-x mod C) + (T mod C) + k*C) (mod m) (for some k)
= a^(x + (-x mod C) + k*C) * a^(T mod C) (mod m)
= a^(x + (-x mod C)) * a^(T mod C) (mod m)
同样，我们将问题简化为相同形式的子问题（“计算T mod C") 和两个简单的模幂。
由于每次迭代中模量至少减少 1，因此我们得到了一个相当弱的界限O(P^(1/2) * min (P, n))对于该算法的运行时间，其中n是堆栈的高度。在实践中，我们应该会变得更好，因为模量预计会呈指数下降。当然这个论点有点夸张，也许一些更喜欢数学的人可以改进它。
有一些边缘情况需要考虑，实际上可以让你的生活变得更轻松：如果出现以下情况，你可以立即停止：m = 1（本例中结果为 0）或者如果a是的倍数m（在这种情况下结果也是 0）。
EDIT:可以证明x = C = phi(m)是有效的，因此作为一种快速而肮脏的解决方案，我们可以使用以下公式
a^T = a^(phi(m) + T mod phi(m)) (mod m)
for T >= phi(m)甚至T >= log_2(m).
