Онлайн-розв'язувач дискретного логарифма
Знайдіть найменший x для g^x ≡ h (mod p) за допомогою повного перебору. Приклад: g=2, h=8, p=13 дає x=3. Обробка виконується локально у вашому браузері.
Почати роботу
Що робить цей інструмент
Інструмент розв'язує задачу дискретного логарифма для невеликих модулів. Він шукає найменший невід'ємний показник x, такий що g^x ≡ h (mod p). Наприклад, для стандартних значень g=2, h=8, p=13, інструмент повертає x=3, оскільки 2^3 = 8, і 8 mod 13 = 8.
Як відбувається обчислення
Алгоритм починає зі значення 1 для x=0 і на кожному кроці множить поточне значення на g за модулем p. Значення h нормалізується за модулем p, тому від'ємні або більші за модуль значення порівнюються за їхнім залишком. Пошук триває до p кроків; якщо збіг не знайдено, інструмент повідомляє про відсутність розв'язку.
Приклад використання
Введіть g=2, h=8, p=13. Очікуваний результат: x=3. Перевірка: 2^3 = 8, 8 mod 13 = 8, отже конгруенція виконується.
Обмеження
Модуль p обмежений значенням від 2 до 1 000 000. Це навчальний інструмент із повним перебором, а не криптографічний сервіс. Він не призначений для реальних криптографічних модулів, оскільки такі обчислення є обчислювально неможливими. Інструмент не доводить, що g є генератором групи, і не перевіряє взаємну простоту. Результат слід перевіряти самостійно для відповідального використання.
Часті запитання
Чи може інструмент працювати з від'ємними значеннями h?
Так, h нормалізується за модулем p, тому від'ємні значення порівнюються за їхнім залишком. Наприклад, якщо p=13, h=-5 буде оброблено як 8 (оскільки -5 mod 13 = 8).
Що станеться, якщо розв'язку не існує?
Якщо після перевірки всіх p можливих значень x (від 0 до p-1) не знайдено жодного збігу, інструмент повідомить, що розв'язку немає. Це може статися, якщо g не є генератором циклічної групи або h не належить до підгрупи, породженої g.
Чи можна використовувати цей інструмент для криптографічних атак?
Ні. Інструмент виконує повний перебір за O(p) кроків, що практично неможливо для великих криптографічних модулів. Він призначений лише для навчальних прикладів із малими числами.
Контрольний список
- Переконайтеся, що p знаходиться в межах від 2 до 1 000 000.
- Вводьте лише цілі числа.
- Після отримання результату перевірте конгруенцію самостійно.
- Пам'ятайте, що інструмент не дає жодних гарантій безпеки.
Обробка виконується локально у вашому браузері.