Дискретний логарифм, Детальна інформація
Дискретний логарифм
. Логарифмуючи останню рівність за основою a, матимемо:
(di - d2i) * logab \xF0BA\xF020(c2i - ci) mod n
Якщо di \xF0B9 d2i (mod n), то це рівняння може бути ефективно розв’язано для обчислення logab.
Алгоритм
Вхід: генератор a циклічної групи G з порядком n та елемент b \xF0CE\xF020G.
Вихід: дискретний логарифм x = logab.
1. x0 \xF0AC\xF0201, c0 \xF0AC\xF0200, d0 \xF0AC\xF0200.
2. for i = 1, 2, ... do
2.1. За значеннями xi-1, ci-1, di-1 та x2i-2, c2i-2, d2i-2 обчислити значення xi, ci, di та x2i, c2i, d2i використовуючи формули (1), (2), (3).
2.2. if (xi = x2i) then
r \xF0AC\xF020(di - d2i) mod n;
if (r = 0) then return (FALSE); // розв’язку не знайдено
x \xF0AC r -1 (ci - c2i) mod n.
return (x).
.
Приклад. Обчислити log29 в групі Z19*.
Побудуємо наступну таблицю значень послідовностей xi, ci, di:
i xi ai bi x2i a2i b2i
1 9 0 1 18 1 1
2 18 1 1 4 4 2
3 17 2 1 4 8 6
4 4 4 2 4 16 14
5 17 4 3 4 32 30
6 4 8 6 4 64 62
На 6 кроці отримали x6 = x12 . Підставивши їх значення, отримаємо:
28 * 96 = 264 * 962 або 28 – 64 = 962 – 6 , 2-56 = 956
Логарифмуємо рівність: -56 * log29 = 56 (mod 18), оскільки |Z19*| = 18.
Враховуючи що -56 (mod 18) \xF0BA\xF02016, 56 (mod 18) \xF0BA\xF0202, перепишемо рівність у вигляді 16 * log29 = 2 (mod 18) або 8 * log29 = 1 (mod 9). log29 = 8-1 (mod 9) = 8.
Відповідь: log29 = 8.
(di - d2i) * logab \xF0BA\xF020(c2i - ci) mod n
Якщо di \xF0B9 d2i (mod n), то це рівняння може бути ефективно розв’язано для обчислення logab.
Алгоритм
Вхід: генератор a циклічної групи G з порядком n та елемент b \xF0CE\xF020G.
Вихід: дискретний логарифм x = logab.
1. x0 \xF0AC\xF0201, c0 \xF0AC\xF0200, d0 \xF0AC\xF0200.
2. for i = 1, 2, ... do
2.1. За значеннями xi-1, ci-1, di-1 та x2i-2, c2i-2, d2i-2 обчислити значення xi, ci, di та x2i, c2i, d2i використовуючи формули (1), (2), (3).
2.2. if (xi = x2i) then
r \xF0AC\xF020(di - d2i) mod n;
if (r = 0) then return (FALSE); // розв’язку не знайдено
x \xF0AC r -1 (ci - c2i) mod n.
return (x).
.
Приклад. Обчислити log29 в групі Z19*.
Побудуємо наступну таблицю значень послідовностей xi, ci, di:
i xi ai bi x2i a2i b2i
1 9 0 1 18 1 1
2 18 1 1 4 4 2
3 17 2 1 4 8 6
4 4 4 2 4 16 14
5 17 4 3 4 32 30
6 4 8 6 4 64 62
На 6 кроці отримали x6 = x12 . Підставивши їх значення, отримаємо:
28 * 96 = 264 * 962 або 28 – 64 = 962 – 6 , 2-56 = 956
Логарифмуємо рівність: -56 * log29 = 56 (mod 18), оскільки |Z19*| = 18.
Враховуючи що -56 (mod 18) \xF0BA\xF02016, 56 (mod 18) \xF0BA\xF0202, перепишемо рівність у вигляді 16 * log29 = 2 (mod 18) або 8 * log29 = 1 (mod 9). log29 = 8-1 (mod 9) = 8.
Відповідь: log29 = 8.
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021