Розв’язати дискретне логарифмічне рівняння виду методом -Полларда.
Розв’язок.
Обчислюватимемо значення з урахуванням того, що
Виберемо С=6 та розрахуємо значення . Результати зведено до таблиці 2.19.
Таблиця 2.19 – Результати розрахунків
І
ri
b=9
ab=20
a2b=1
a2b2=9
a3b2=20
a4b2=1
a4b3=9
Ui
Vi
Аналізуючи значення , ми бачимо, що r1= r4= r7, r2= r5, r3= r6. Вибравши будь-яку пару та , знайдемо пари значень та . Наприклад, для r3=r6 маємо при r3. Ui=2 і Vi=2, для r6 Uj=4 і Vj=3. Підставивши ці значення в (2.79), маємо
.
Далі знайдемо зворотний елемент y для числа 21 в кільці за модулем 22. Маємо рівняння
.
Розв’яжемо це рівняння, використовуючи алгоритм Евкліда
отже тоді
Таким чином, Прямим обчисленням перевіряємо пра-вильність розв’язку.
Розв’язати дискретне логарифмічне рівняння виду
Розв’язок.
Зробимо, використовуючи метод Поліга-Хеллмана. Розкладаємо число
Отже
Оскільки максимальні значення ступеня залишку і , то згідно з (2.84) та лишки матимуть лише два члени. Тому шукатимемо та лишки за модулями та відповідно
Тепер нам потрібно знайти та Для цього використаємо порівняння (2.94), в результаті отримаємо
або
обчисливши ліву частину, маємо
.
Тепер врахуємо, що коефіцієнти та , обчислюються за модулем 2, то або Підставивши ці значення, отримаємо, що Для знаходження використаємо порівняння (2.94), в результаті отримаємо