29.3 (7.2.3) Метод Поліга-Геллмана дискретного логарифмування

Метод Поліга-Геллмана дискретного логарифмування базується на китайській теоремі про лишки [13, 422, 426]. Він може бути реалізований з експоненційною складністю у разі якщо відомо розклад числа Р-1.

Нехай знову необхідно розв’язати порівняння (дискретний логарифм) вигляду

. (9.45)

Розв’язання виконується в декілька етапів:

1. знаходиться канонічний розклад числа Р-1;

2. обчислюються лишки за модулями канонічного розкладу;

3. обчислюється значення Х згідно з китайською теоремою про лишки.

Перший етап виконується достатньо просто, оскільки на етапі побудови пари розклад числа Р-1 є відомим. Інакше довести, що а – породжуючий (твірний) елемент, дуже складно. Тому на першому етапі Р-1 подається у вигляді:

(9.46)

Далі знайдемо лишки від ділення Х на , у результаті для кожного отримаємо:

, (9.47)

причому .

Необхідно знайти коефіцієнти для всіх i. Оскільки лишки подано за модулем , то

. (9.48)

Запишемо далі (9.45) у вигляді

. (9.49)

та піднесемо ліву і праву частини (9.49) до степеня . У результаті отримаємо:

. (9.50)

Обчислимо значення , підставивши в нього (9.48), у результаті маємо:

. (9.51)

Якщо перемножити на вираз у дужках, отримаємо:

. (9.52)

У цьому можна переконатися, оскільки всі члени, окрім , діляться на Р-1, тому вони даватимуть лишок, який дорівнює 0. З урахуванням (9.52) вираз (9.50) має вигляд:

. (9.52)

Тепер піднесемо ліву та праву частини (9.49) до степеня , у результаті отримаємо:

. (9.53)

Підставивши у (9.53) вираз (9.48), отримаємо:

. (9.54)

Оскільки на (Р-1) тепер не ділитимуться два члени

та ,

тому вони не дорівнюють нулю.

Аналогічно можна перетворити (9.49) для всіх і для усіх степенів. У результаті для конкретного модуля степеня отримаємо порівнянь:

(9.55)

Використовуючи (9.55), можна знайти всі лишки вигляду (9.46), для цього достатньо знайти коефіцієнти . Їх ми знаходимо, використовуючи (9.55). Спочатку, перебираючи значення , знаходимо і так далі для всіх степенів, до включно.

Таким чином, для фіксованого система (9.55) дозволяє визначити коефіцієнти і, як наслідок, лишок (9.47). Для знаходження другого лишку необхідно взяти наступне значення .

Таким чином, ми одержуємо лишки:

(9.56)

Використовуючи китайську теорему про лишки, отримаємо [422, 13]:

, (9.57)

де

Зворотний елемент знаходимо із порівняння

.

Таким чином, (9.57) дає розв’язок дискретного логарифмічного порівняння вигляду (9.45) або (9.34).

Приклад 9.5 дискретного логарифмування в скінченному полі Галуа

Розв’язати дискретне логарифмічне рівняння вигляду Використовуючи метод Поліга-Геллмана, що викладений вище маємо.

Спочатку розкладаємо число

Отже

Оскільки максимальні значення степеня лишку і , то згідно з (9.46) та лишки матимуть тільки два члени. Тому шукатимемо та лишки за модулями та відповідно:

Тепер нам потрібно знайти та Для цього використаємо порівняння (9.55), у результаті отримаємо:

або _.

Обчисливши ліву частину, маємо:

.

Далі, враховуючи, що коефіцієнти та обчислюються за модулем 2, маємо, що або Підставивши ці значення, отримаємо, що Для знаходження використовуємо порівняння (9.55), у результаті отримаємо:

.

Після обчислень маємо:

та .

Отже, Таким чином,

Далі за аналогією знайдемо , для цього знайдемо та . Як і для , маємо:

або

Підставимо у перше порівняння послідовно

(оскільки ).

За аналогією, як і для та , маємо: ,

тому

Тепер, знаючи лишки та , можна знайти Х, використовуючи формулу (9.57):

Таким чином, .