Дискретний логарифм (стр. 2 из 2)

2. Побудувати систему лінійних рівнянь, розв’язком якої будуть значення log_ap_i. Для цього виконаємо наступні кроки:

2.1. Обрати деяке ціле k, 0 £ k£ n - 1 та обчислити a^k .

2.2. Спробувати представити значення a^k у вигляді добутку чисел з S:

a^k = , c_i³ 0

Якщо така рівність знайдена, то записати рівняння:

k = (mod n)

2.3. Повторювати кроки 2.1. та 2.2. поки не отримаємо t + cлінійних рівнянь. Невелике ціле число c (1 £c£ 10) обирається таким чином, щоб складена система рівнянь мала єдиний розв’язок з великою ймовірністю (якщо скласти лише t рівнянь з t невідомими, то з великою ймовірністю два з цих рівнянь будуть залежними і тоді система буде мати більше одного розв’язку).

3. Розв’язати утворену систему рівнянь, отримати значення log_ap_i, 1£i£t.

4. Обчислення log_ab.

4.1. Обрати деяке ціле k, 0 £ k£ n - 1 та обчислити b*a^k .

4.2. Спробувати представити значення b*a^k у вигляді добутку чисел з S:

b*a^k = , d_i³ 0

Якщо такого представлення знайти не вдається, виконати знову 4.1. Інакше прологарифмірувавши останню рівність, отримаємо:

x = log_ab = ( - k) mod n

Приклад. Обчислити log₂12 в групі Z₁₉^*.

1. Нехай S = {2, 3, 5} – множникова основа.

2. Будуємо систему рівнянь для знаходження значень log₂p_i, де p_iÎS. Оскільки множина S містить 3 елементи, то достатньо отримати 3 лінійно незалежні рівняння.

k = 5: 2⁵ (mod 19) º13 – не представимо у вигляді добутку чисел з S.

k = 7: 2⁷ (mod 19) º14 – не представимо у вигляді добутку чисел з S.

k = 2: 2² (mod 19) º4 = 2². Перше рівняння: 2 = 2log₂2.

k = 10: 2¹⁰ (mod 19) º17 – не представимо у вигляді добутку чисел з S.

k = 15: 2¹⁵ (mod 19) º12 = 2² * 3. Друге рівняння: 15 = 2log₂2 + log₂3.

k = 11: 2¹¹ (mod 19) º15 = 3 * 5. Третє рівняння: 11 = log₂3 + log₂5.

3. Система рівнянь за модулем 18 (порядок Z₁₉^* дорівнює 18) має вигляд:

Її розв’язком буде:

log₂2 = 1, log₂3 = 13, log₂5 = 16

4. Обчислення log₂12.

k = 3: 12 * 2³(mod 19) º 1 – не представимо у вигляді добутку чисел з S.

k = 7: 12 * 2⁷ (mod 19) º16 = 2⁴.

log₂12 + 7 º 4log₂2 (mod 18), log₂12 º (4log₂2 – 7) (mod 18) = 15.

Відповідь: log₂12 = 15.

Алгоритм Поліга – Хелмана

Алгоритм Поліга – Хелмана ефективно розв’язує задачу дискретного логарифма в групі G порядка n, якщо число n має лише малі прості дільники.

Нехай g, hÎG, |G| = p^s, p – просте. Тоді значення x = log_gh можна подати у вигляді:

x = x₀ + x₁p + x₂p² + … + x_s-1p^s-1

Піднесемо рівняння h = g^xдо степеняp^s-1:

= = =

* * * … * = ,

оскільки = 1 (g – генератор групи, p^s – її порядок).

Таким чином з рівності = знаходимо x₀.

Далі маючи значення x₀, x₁, …, x_i-1можна обчислити x_iз рівняння

=

Приклад. Обчислити log₃7 в Z₁₇^*.

Необхідно розв’язати рівняння 3^x = 7 в групі, порядок якої дорівнює 16 = 2⁴.

Представимо x у двійковій системі числення: x = x₀ + 2x₁ + 4x₂ + 8x₃.

1. Обчислення x₀.

Піднесемо рівняння 3^x = 7 до степеня 2³ = 8:

= 7⁸, = -1,

* * * = -1.

Оскільки 3¹⁶ (mod 17) º 1, тоостаннє рівняння прийме вигляд = -1. Враховуючи що 3⁸ (mod 17) º -1, маємо: = -1, x₀ = 1.

2. Обчислення x₁.

Домножимо рівність = 7 на = 3^-1 (mod 17) = 6, отримаємо:

= 7 * 6 або = 8.

Піднесемо рівняння до степеня 4: = 8⁴, = -1, x₁ = 1.

3. Обчислення x₂.

1. D. Shanks. Class number, a theory of factorization and genera. In Proc. Symposium Pure Mathematics, vol.20, pp.415-440. American Mathematical Society, 1970.