修正几何级数中的模运算

Question

我们知道几何级数中 n 项的总和为 Sn = a1(1-r^n)/(1-r) 如果级数的形式为 a1, a1*r, a1*r^2, a1*r^3....a1*r^n。

现在我有mod化的几何级数，其中级数的形式是 a1, (a1*r) mod p , (a1*r^2) mod p, (a1*r^3) mod p.....(a1*r ^n)mod p 其中a1是初始项，p是素数，r是公比。该系列的第 N 项由下式给出：(a1 * r^n-1) mod p.

我正在尝试获取上述 mod 化 GP 的求和公式并且非常努力。如果任何人都可以对此有所了解或建议找到有效的算法来查找总和而不对所有 n 项进行迭代，将会有很大帮助。

Answer 1

主关系相同，和x就是

的解

a1*(r^N-1) = (r-1)*x mod p.

难观察的是p和r-1可能有公约数，这不是真正的问题，因为r-1除以r^N-1，但仍然需要小心处理。

模除法可以通过与逆相乘来实现，并且可以通过扩展欧几里得算法计算。

的任意实现

 d,u,v = XGCD(r-1,p)

returns 最大公约数 d 和 Bezout 因数 u,v 因此

u*(r-1)+v*p = d

与f/d、f = a1*(r^N-1)相乘得到

(u*f/d)*(r-1) + (v*f/d)*p = f = a1*(r^N-1)

使得解可以识别为x = u*(f/d)。因此，实现将遵循

的行

 rN = powmod(r,N,p)
 f = a1*(rN-1) mod p

 d,u,v = XGCD(r-1,p)

 return u*(f/d) mod p

Answer 2

请注意，如果 r 是 primitive root modulo p。然后我们可以降低求和的复杂度。

我们必须找到 S = a1*1 + a1*r + a1*r^2 + ... + a1*r^n。然后我们将 S 写成 S = a1*(r^n - 1) / (r - 1) 的封闭形式。

现在可以减少为：

 a1*(r^n - 1) / (r - 1) = S (mod p)
=> a1*r^n = S * (r - 1) + 1 (mod p)

现在取两边都以r为底的离散对数，

   log(a1*r^n) = log_r(S*(r-1) + 1 (mod p))
   =>log_r(a1) + n*log_r(r) = log_r(S*(r-1) + 1 (mod p))
   =>n*log_r(r) = log_r(S*(r-1) + 1 (mod p)) - log_r(a1) (mod(p-1))
   =>n*1 = log_r(S*(r-1) + 1 (mod (p-1))) - log_r(a1) (mod (p-1))

请注意，如果 a1 是 1，则最后一项是 0。

设 S = 6，r = 3，m = 7，a1 = 1。然后，我们要在以下同余中求解 n：

     (3^n - 1)/(3 - 1) = 6 (mod 7)
=> 3^n - 1 = (3 - 1) * 6 (mod 7)
=> 3^n = 2 * 6 + 1 (mod 7)
=> 3^n = 6 (mod 7)

然后我们取两边的discrete logarithm：

     log_3(3^n) = log_3(6) (mod (7-1))
=> n * log_3(3) = log_3(6) (mod 6)
=> n * 1 = 3 (mod 6)
=> n = 3 (mod 6)

所以，n = 3。

您可以使用Baby-step Giant-step算法在O(sqrt(m))中解决这个问题。如果你想在代码中实现，我会提供给你。

修正几何级数中的模运算

Modulo Arithmetic in Modified Geometric Progression

algorithm

math

modulo

algebra