有效的除法求幂

Question

我需要计算 计算模数下线性变换的重复应用。

((a ** p - 1) // (a - 1)) % m == ((pow(a, p, x) - 1) // (a - 1)) % m

在给定 a、p 和 m 的情况下，我怎样才能找到一个可以工作的 x 呢？难道只是x = ((a - 1) * m)吗？它们都是整数，并且 m 是素数。只是 a ** p 太大了，计算起来很慢，而且没有必要。

我正在尝试计算线性变换的组成。假设有两个函数：

A = lambda x: (a * x + b) % m
B = lambda x: (c * x + d) % m

组合它们很简单。但计算 A 的重复应用正是我想要做的。将函数 C 定义为 A(x) == C(A, 1)(x), A(A(x)) == C(A 、 2)(x)、A(A(A(x))) == C(A, 3)(x) 等等。 B 也可以。

C(A, n)(x) == (pow(a, n, m) * x + b * ((a ** n - 1) // (a - 1))) % m
C(B, n)(x) == (pow(c, n, m) * x + d * ((c ** n - 1) // (c - 1))) % m

我并不是想反算A。我正在尝试转发计算C。