Расчет количества слагаемых, которые нужно сложить, чтобы последовательно получить требуемую сумму

У меня геометрическая прогрессия, как у серии:

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 не сработает, потому что он слишком велик и, следовательно, требует много времени до завершения.

Я обнаружил аналогичную проблему здесь. Но в этой ссылке на r нет свойства сделать алгоритм быстрее. Я применил все приведенные здесь ответы к своему коду, но ни один из них не снижает его сложность должным образом.

Я знаю, что каким-то образом мне нужно использовать свойство r, чтобы создать эффективный алгоритм, но я не знаю, как это сделать.

Итак, есть ли какой-либо другой шаблон, который мы можем найти, или какое-либо использование этого свойства, которое мы можем сделать, чтобы получить наиболее эффективный алгоритм? (Обычно я не хочу повторять m.) Поэтому, пожалуйста, дайте мне представление об эффективном алгоритме поиска n.


python series algorithm time-complexity number-theory
person Daemon    schedule 17.06.2017    source источник
comment
Вы написали: r,r^2,....r^(n-1) then it will contain all the numbers [from] 1 to m-1. Вы имеете в виду r (mod m), r^2 (mod m), ..., r^(n-1) (mod m)?   -  person ljeabmreosn    schedule 18.06.2017
comment
@ljeabmreosn Да! Я обновил это, чтобы другие не сомневались! :) PS: И это m не n во власти.   -  person Daemon    schedule 18.06.2017
comment
Кроме того, xi = (x(i-1))*r (mod m) for i>1 and x1=1 не подразумевает, что S = 1 + r + r^2 + r^3 + ... + r^n (mod m)?   -  person ljeabmreosn    schedule 18.06.2017
comment
Можем ли мы поговорить где-нибудь, чтобы я мог показать вам фотографии? Если a1 + (a1*r)%m + ((a1*r)%m*r)%m + ... . Здесь, если я возьму 3-й член .... тогда вы можете написать ((a1%m)*(r%m))%m * (r%p))%m = (a*r^2)%m...So a1 + (a1*r)%m + (a1*r^2)%m.. a1*r^(n-1)%m.... = ›Ваш результат до r^(m-1), хотя ... тогда вы можете заменить их суммой 1 to m-1. Я подумал, что и найти сумму, но тем не менее, он завершался раньше, чем требуется, и в некоторых тестовых случаях показывал неправильные результаты. Мы можем поговорить в facebook или gmail ??   -  person Daemon    schedule 18.06.2017
comment
Я не могу, потому что у меня должна быть репутация 20, чтобы общаться там. Я новичок в stackoverflow.   -  person Daemon    schedule 18.06.2017
comment
Спасибо. Я отправил тебе письмо.   -  person Daemon    schedule 18.06.2017
comment
Текущий вопрос конкурса. ССЫЛКА < / b>   -  person Sanket Makani    schedule 18.06.2017

Ответы (1)


arrow_upward
0
arrow_downward

Я считаю, что нашел решение. Обратите внимание, что r - это примитивный корень по модулю m заданным свойством r.

Рассмотрим геометрическую сумму S = 1 + r + r^2 + ... + r^n. Затем записываем S в закрытом виде как S = (r^n - 1) / (r - 1).

Что ж, мы хотим решить это уравнение по модулю m для n, поскольку нам уже даны S и r. Итак, нам нужно решить:

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

Теперь мы столкнулись с проблемой дискретного логарифма.

Используя алгоритм 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)
person ljeabmreosn    schedule 18.06.2017