Fotools
EN

Решение уравнений сравнений

Входные параметры

Быстрый пример:

Результат вычисления

Введите параметры и нажмите «Решить уравнение»

Описание алгоритма:

1. Линейное уравнение ax ≡ b (mod m):
  • Существование решений:Уравнение имеет решение тогда и только тогда, когда gcd(a, m) делит b (т.е. b делится на gcd(a, m))
  • Количество решений:Если решения существуют, то есть d = gcd(a, m) различных решений по модулю m
  • Метод решения:
    1. Вычислить d = gcd(a, m)
    2. Проверить, делит ли d число b; если нет, то решения нет
    3. Разделить обе части уравнения на d: (a/d)x ≡ (b/d) (mod m/d)
    4. Использовать расширенный алгоритм Евклида для нахождения обратного элемента a/d по модулю m/d
    5. Вычислить x₀ = a⁻¹ × (b/d) mod (m/d)
    6. Общее решение: x = x₀ + k(m/d), где k = 0, 1, ..., d-1
2. Показательное уравнение a^x ≡ b (mod m) (задача дискретного логарифма):
  • Описание задачи:Даны a, b, m, найти наименьшее неотрицательное целое x, такое что a^x ≡ b (mod m)
  • Существование решений:
    • Если gcd(a, m) = 1 и b является элементом циклической группы, порождённой a по модулю m, то решение существует
    • Метод проверки: перебор степеней a, пока не будет найдено b или не завершится полный цикл
  • Метод решения:
    • Полный перебор в небольшом диапазоне:Перебор x = 0, 1, 2, ... пока не будет найдено решение или не достигнут предел поиска
    • Алгоритм «встреча посередине» (Baby-step giant-step):Временная сложность O(√m), подходит для задач среднего размера
    • Ро-алгоритм Полларда:Применим для больших простых модулей
  • Периодичность:Если x₀ — решение, то x = x₀ + kφ(m) также является решением (где φ(m) — функция Эйлера)
3. Области применения:
  • Криптография:RSA, обмен ключами Diffie-Hellman, шифрование ElGamal
  • Теория чисел:Первообразные корни, квадратичные вычеты, китайская теорема об остатках
  • Генерация случайных чисел:Линейный конгруэнтный генератор (LCG)
  • Хеш-функции:Применение модульной арифметики в хеш-таблицах
  • Спортивное программирование:Быстрое возведение в степень, обратный элемент по модулю, задачи теории чисел

Сложность алгоритмов:

  • Линейные уравнения:O(log m) (сложность расширенного алгоритма Евклида)
  • Показательные уравнения (полный перебор):O(n), где n — предел поиска
  • Показательные уравнения (BSGS):O(√m), требуется дополнительная память

Важные теоремы:

  • Теорема Безу:Уравнение ax + my = gcd(a, m) всегда имеет целочисленные решения
  • Малая теорема Ферма:Если p — простое и gcd(a, p) = 1, то a^(p-1) ≡ 1 (mod p)
  • Теорема Эйлера:Если gcd(a, m) = 1, то a^φ(m) ≡ 1 (mod m)
  • Китайская теорема об остатках:Позволяет решать системы сравнений