修正几何级数的模运算 [英] Modulo Arithmetic in Modified Geometric Progression

问题描述

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

We know that sum of n terms in a Geometric Progression is given by Sn = a1(1-r^n)/(1-r) if the series is of the form a1, a1*r, a1*r^2, a1*r^3....a1*r^n.

现在，我修改了级数形式的几何级数 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.

Now i have modified geometric progression where series is of the form a1, (a1*r) mod p , (a1*r^2) mod p, (a1*r^3) mod p.....(a1*r^n)mod p where a1 is the initial term, p is prime number and r is common ratio. Nth term of this series is given by: (a1 * r^n-1) mod p.

我正在尝试获取上述经过修改的GP的求和公式，并且非常努力.如果有人可以对它有所启发，或者在不迭代所有n个项的情况下找到有效的求和算法的建议，将大有帮助.

I am trying to get summation formula for above modified GP and struggling very hard. If anyone can throw some light on it or advice on finding efficient algorithm for finding sum without iterating for all the n terms, will be of great help.

推荐答案

请注意，如果r是原始根模p . 然后，我们可以降低总和的复杂度.

Note that if r is a primitive root modulo p. Then we can reduce complexity of the sum.

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

We have to find S = a1*1 + a1*r + a1*r^2 + ... + a1*r^n. Then we write S in the closed form as 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的离散对数，

Now take discrete logarithm with base r both sides,

   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.

Note that if a1 is 1 then the last term is 0.

让S = 6，r = 3和m = 7，a1 = 1. 然后，我们要在以下等式中求解n:

Let S = 6, r = 3, and m = 7, a1 = 1. Then, we want to solve for n in the following congruence:

     (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)

然后我们采用双方的离散对数:

     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))中. 如果您想用代码实现，我会为您提供.

You can use Baby-step Giant-step algorithm to solve this in O(sqrt(m)). If you want implementation in code I will provide you.

这篇关于修正几何级数的模运算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！