Блог пользователя stostap

Дискретное логарифмирование
Автор stostap, 13 лет назад, По-русски

Помогите пожалуйста решить задачу когда a i m не взаимно просты.
Для взаимно простых есть статья http://e-maxx.ru/algo/discrete_log где сказаночто алгоритм можно модифицировать ... не придумал как :(((

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

Есть мнение, что для существования решения необходимо и достаточно, чтобы b делилось на НОД(a,m), тогда можно m разделить на НОД, а b сделать таким, чтобы правильное решение подходило под новое уравнение.
upd.А дальше есть несколько пока не устраненных мной проблем.
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Это необходимое условие, но уж точно не достаточное. Например, если взять уравнение:
    2x = 6 (mod 8)
    6 делится на 2, но решения не существует. 
    Да и после деления m на НОД мы-то можем решить уравнение, но таким образом все корни мы не найдем.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Да, это я тоже забыл исправить. Я думал опираться на КТО, но она требует взаимную простоту модулей, а НОД и m/НОД могут оказаться не взаимно просты и появятся проблемы. Так сходу простого решения проблем не видно.
      → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
      надо найти минимальное положительное решения
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Чтож вы так крупно разговариваете? Просто мы пропустим несколько решений, причем легко можем пропустить минимальное.
        → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Сокращаем m на НОД(а,m), пока можем, а затем решаем уравнение для взаимнопростых. Только при решении того уравнения мы проверяем, чтобы решение подходило под исходное уравнение.

        Можно показать что мы найдем минимальный корень таким образом.
        → Ответить
        • 8 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          Ваш комент похоже единственный в рунете поясняет как доработать Шенкса для произвольных чисел (если правильно Вас понял: если b не делиться на gcd(a,m) то нет решений, иначе взять gcd(a,m) если он отличен от 1 делить m на него пока нет остатка, а потом взять b по модулю m. Решать с ними и как встретится решение для новых b и m, то проверить его для старых переменных? эта задача зашла этим способом). Не подскажите где Вы нашли это замечание или если не помните, то почему оно работает?

          → Ответить
          • 8 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            Если корень есть, то мы его таким образом обязательно найдем, т.к. если a = b(mod m), то и если m делится на k. Количество корней мы таким образом увеличим, так что нужно обязательно каждый корень проверить на то, подходит ли он под исходное уравнение.

            → Ответить
»
13 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Пусть надо найти дискретный логарифм b по основанию а по модулю m. (a^x = b (mod m)) Пусть p_1, p_2, p_3, ..., p_k — все общие простые делители у a и m. Пусть число n получается из числа m делением на все простые p_1 ... p_k в максимальной степени.

То есть m = n * (p_1 ^ M_1) * (p_2 ^ M_2) * ... * (p_k ^ M_k), где M_1 ... M_k — степени вхождения соответствующего простого в M. Аналогично определим A_1 ... A_k и B_1 ... B_k для чисел a и b соответственно.

1 случай) Для некоторого i от 1 до k B_i < M_i. Тогда, поскольку A_i >= 1, при x >= (B_i + 1) / A_i a^x кратно p_i ^ (B_i + 1), а b — нет. Значит, a^x != b (mod m) при x >= (B_i + 1) / A_i . Значит, достаточно перебрать все x < (B_i + 1) / A_i.

2 случай) Для всех i от 1 до k B_i >= M_i. Тогда решаем a^x = m (mod n) (Теперь a и модуль взаимно просты). Если нет решений, то нет и у исходной задачи. Если решение x нашлось, то прибавляем к х ф(n) (функция Эйлера), пока не станет x >= max(M_i / A_i). Тогда остаток a^x mod n не поменяется, а на все p_i ^ M_i начнёт делиться. Значит, будет a^x = b (mod m).

Асимптотика:

Вычисление n, p_i, A_i, B_i, M_i: O(sqrt(m)).

1 cлучай: O(log(m)).

2 случай: дискретное логарифмирование O(sqrt(n)log(n)) + прибавление ф(n) O(log(m)) = O(sqrt(m)log(m)).

Итого: O(sqrt(m)log(m)).

При этом в обоих случаях ответ x помещается в диапазон [0; m):

1 случай: x < B_i + 1 <= m (ведь m >= 2^B_i >= B_i + 1).

2 случай: x < max(M_i / A_i) + ф(m) <= max(M_i) + ф(n) <= [log2(m / n)] + ф(n) <= m — 1, поскольку если [log2(m / n)] = t, то m >= n * 2^t, тогда m — 1 >= n * 2^t — 1 >= n + 2^t — 2 = (2^t — 1) + (n — 1) >= t + ф(n) = [log2(m / n)] + ф(n).

→ Ответить