计算应添加的项数以获得所需的系列总和

Question

我有一个几何级数的系列：

S = x1 + x2 + .....    xn (mod m)
where xi = (x(i-1))*r (mod m) for i>1 and x1=1  , 2<=m<10^9, 1<=r<m, 1<=S<m, 1<=n<p

这里m是素数，r,m,S已知

Property of r : If we form a set of r (mod m), r^2 (mod m), ..., r^(m-1) (mod m) then it will contain all the numbers form 1 to m-1.

我想找到 n 的值（如果可能的话）。我不能在这里应用几何级数 (GP) 公式，所以我做了一个替代算法，假设这些幂将使一个周期的长度比 n-1 小得多。我想找到一种模式，使系列重复自身，但这种循环模式只发生在某些 r's 中，所以我没有这样做。当然，设置一个循环直到 m 的天真的方法是行不通的，因为它太大了，因此在终止之前花费了大量时间。

我发现了一个类似的问题here。但是在这个 link 中没有 r 上的属性来使算法更快。我将此处给出的所有答案应用到我的代码中，但 none 正在根据需要降低其复杂性。

我知道我必须以某种方式使用 r 的属性来制作一个有效的算法，但我不知道如何。

那么我们是否可以找出任何其他模式或使用此属性来获得最有效的算法？（基本上我不想遍历 m。）所以请给我一个找到 n.

的有效算法的想法

Answer 1

我相信我已经找到了解决办法。请注意，r 是由 r 的属性给出的 primitive root modulo m。

考虑几何和S = 1 + r + r^2 + ... + r^n。然后我们将 S 写成 S = (r^n - 1) / (r - 1) 的封闭形式。

好吧，因为我们已经给出了 S 和 r，所以我们想对 n 求模 m 来求解这个方程。所以我们需要解决：

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

我们现在已经运行进入了Discrete Logarithm Problem。

使用Baby-step Giant-step算法，我们可以在O(sqrt(m))中解决这个问题，如果m最多为10^9，这是可行的。下面是我在 Python 3 中的实现，其中 answer(r, m, S) 给出了所需的答案：

from math import sqrt, ceil

def invmod(r, p):
    """
    solves x = r^(-1) modulo p
    Note: p must be prime
    """
    return pow(r, p-2, p)


def discrete_log(a, r, p):
    """
    solves r^x = a (mod m) for x
    using the baby-step giant-step algorithm:
    https://math.berkeley.edu/~sagrawal/su14_math55/notes_shank.pdf
    Note: r must be a primitive root modulo p
    """


    m = int(ceil(sqrt(p)))

    # compute 1, r, r^2, ..., r^(m-1) modulo p
    pows = {pow(r, mp, p): mp for mp in range(m)}

    # compute r^(-m) modulo p
    y = pow(invmod(r, p), m, p)

    # compute a, ay, ay^2, ..., until we find a number
    # already in pows
    for q in range(m):
        z = (a * pow(y, q, p)) % p
        if z in pows:
            return pows[z] + (q * m)

    raise Exception("discrete logarithm not found")


def answer(r, p, S):
    """
    if S = 1 + r + r^2 + ... + r^n (mod p),
    then answer(r, p, S) = n
    """
    a = (S * (r-1) + 1) % p
    return discrete_log(a , r, p)

计算应添加的项数以获得所需的系列总和

Calculating number of terms that should be added to get the required sum in series

python

algorithm

series

time-complexity

number-theory