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)
  • Китайська теорема про остачі:Може розв'язувати системи конгруенцій