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

Question

I have a geometric progression like series:

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

here m is a prime number and r,m,S are known.

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.

I want to find the the value of n (if possible). I cannot apply the Geometric Progression (GP) formula here so I made an alternate algorithm making an assumption that these powers will make a cycle of length much smaller than n-1. I thought to find a pattern such that the series repeats itself but this pattern of cycle occurs only for some r's so I failed to do so. Of course, naive approach of setting a loop till m wont work because it's too large and hence took a large amount of time before terminating.

I found a similar problem here. But in this link there is no property on r to make the algorithm faster. I applied all the answers given here to my code but none is reducing its complexity as required.

I know that somehow I have to use property of r to make an efficient algorithm but I don't know how.

So is there any other pattern we can find out or any use of this property we can make to get the most efficient algorithm? (Basically I don't want to iterate over m.) So please give me an idea of an efficient algorithm to find the n.

Answer 1

I believe I have found a solution. Note that r is a primitive root modulo m by the property of r given.

Consider the geometric sum S = 1 + r + r^2 + ... + r^n. Then we write S in the closed form as S = (r^n - 1) / (r - 1).

Well, we want to solve this equation modulo m for n as we are already given S and r. So we need to solve:

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

We have now run into the Discrete Logarithm Problem.

Using the Baby-step Giant-step algorithm, we can solve this in O(sqrt(m)) which is doable if m is at most 10^9. Below is my implementation in Python 3 where answer(r, m, S) gives the desired answer:

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)