Рассчитать дискретный логарифм

Question

Учитывая положительные целые числа b, c, m, где (b < m) is True это найти положительное целое число e такое, что

(b**e % m == c) is True

где ** - возведение в степень (например, в Ruby, Python или ^ в некоторых других языках), а% - операция по модулю. Какой наиболее эффективный алгоритм (с наименьшей сложностью big-O) для его решения?

Пример:

Дано b = 5; с = 8; m = 13 этот алгоритм должен найти e = 7, потому что 5 ** 7% 13 = 8

Answer 1

От оператора% я предполагаю, что вы работаете с целыми числами.

Вы пытаетесь решить проблему дискретного логарифма . Разумным алгоритмом является Baby step, гигантский шаг , хотя есть много других, ни один из которых не является особенно быстрым.

Сложность поиска быстрого решения проблемы дискретного логарифма является фундаментальной частью некоторых популярных криптографических алгоритмов, поэтому, если вы найдете лучшее решение, чем любое из них в Википедии, пожалуйста, дайте мне знать!

Answer 2

Это совсем не простая проблема. Это называется вычислением дискретного логарифма , и это обратная операция к модульному показателю .

Эффективный алгоритм не известен. То есть, если N обозначает количество бит в m, все известные алгоритмы выполняются в O (2 ^ (N ^ C)), где C> 0.

Answer 3

Поскольку дубликат этого вопроса был задан под тегом Python, здесь приведена реализация на Python гигантского шага baby step, который, как указывает @MarkBeyers, является разумным подходом (если модуль не слишком большой):

def baby_steps_giant_steps(a,b,p,N = None):
    if not N: N = 1 + int(math.sqrt(p))

    #initialize baby_steps table
    baby_steps = {}
    baby_step = 1
    for r in range(N+1):
        baby_steps[baby_step] = r
        baby_step = baby_step * a % p

    #now take the giant steps
    giant_stride = pow(a,(p-2)*N,p)
    giant_step = b
    for q in range(N+1):
        if giant_step in baby_steps:
            return q*N + baby_steps[giant_step]
        else:
            giant_step = giant_step * giant_stride % p
    return "No Match"

В приведенной выше реализации явный N может быть передан в fish для небольшого показателя степени, даже если p криптографически велик. Он будет находить показатель степени, пока показатель меньше, чем N**2. Если N опущен, показатель всегда будет найден, но не обязательно в вашей жизни или в памяти вашей машины, если p слишком велик.

Например, если

p = 70606432933607
a = 100001
b = 54696545758787

тогда 'pow (a, b, p)' оценивается как 67385023448517

и

>>> baby_steps_giant_steps(a,67385023448517,p)
54696545758787

Это заняло около 5 секунд на моей машине. Для показателя степени и модуля этих размеров я оцениваю (основываясь на временных экспериментах), что грубая сила заняла бы несколько месяцев.

Answer 4

Дискретный логарифм - сложная проблема

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

Я добавлю здесь простой алгоритм грубой силы, который пробует каждое возможное значение от 1 до m и выводит решение, если оно было найдено. Обратите внимание, что может быть более одного решения проблемы или ноль решений вообще. Этот алгоритм вернет вам наименьшее возможное значение или -1, если его не существует.

def bruteLog(b, c, m):
    s = 1
    for i in xrange(m):
        s = (s * b) % m
        if s == c:
            return i + 1
    return -1

print bruteLog(5, 8, 13)

и здесь вы можете увидеть, что 3 на самом деле является решением:

print 5**3 % 13

Существует лучший алгоритм, но поскольку его часто просят реализовать на соревнованиях по программированию, я просто дам вам ссылку на объяснение .

Answer 5

как сказал, общая проблема трудна. однако, простой способ найти e, если и только если вы знаете, что e будет маленьким (как в вашем примере), это просто попробовать каждое e из 1.

Между прочим, e == 3 - это первое решение для вашего примера, и вы, очевидно, можете найти это за 3 шага по сравнению с решением недискретной версии и наивным поиском целочисленных решений, т.е.

e = log (c + n * m) / log (b) где n - неотрицательное целое число

, который находит e == 3 за 9 шагов