Дискретний логарифм, Детальна інформація
Дискретний логарифм
, ci \xF0B3\xF0200
Якщо така рівність знайдена, то записати рівняння:
(mod n)
2.3. Повторювати кроки 2.1. та 2.2. поки не отримаємо t + c лінійних рівнянь. Невелике ціле число c (1 \xF0A3 c \xF0A3 10) обирається таким чином, щоб складена система рівнянь мала єдиний розв’язок з великою ймовірністю (якщо скласти лише t рівнянь з t невідомими, то з великою ймовірністю два з цих рівнянь будуть залежними і тоді система буде мати більше одного розв’язку).
3. Розв’язати утворену систему рівнянь, отримати значення logapi, 1\xF0A3 i \xF0A3 t.
4. Обчислення logab.
4.1. Обрати деяке ціле k, 0 \xF0A3\xF020k \xF0A3\xF020n - 1 та обчислити b * ak .
4.2. Спробувати представити значення b * ak у вигляді добутку чисел з S:
, di \xF0B3\xF0200
Якщо такого представлення знайти не вдається, виконати знову 4.1. Інакше прологарифмірувавши останню рівність, отримаємо:
- k) mod n
Приклад. Обчислити log212 в групі Z19*.
1. Нехай S = {2, 3, 5} – множникова основа.
2. Будуємо систему рівнянь для знаходження значень log2pi, де pi \xF0CE\xF020S. Оскільки множина S містить 3 елементи, то достатньо отримати 3 лінійно незалежні рівняння.
k = 5: 25 (mod 19) \xF0BA 13 – не представимо у вигляді добутку чисел з S.
k = 7: 27 (mod 19) \xF0BA 14 – не представимо у вигляді добутку чисел з S.
k = 2: 22 (mod 19) \xF0BA 4 = 22. Перше рівняння: 2 = 2log22.
k = 10: 210 (mod 19) \xF0BA 17 – не представимо у вигляді добутку чисел з S.
k = 15: 215 (mod 19) \xF0BA 12 = 22 * 3. Друге рівняння: 15 = 2log22 + log23.
k = 11: 211 (mod 19) \xF0BA 15 = 3 * 5. Третє рівняння: 11 = log23 + log25.
3. Система рівнянь за модулем 18 (порядок Z19* дорівнює 18) має вигляд:
Її розв’язком буде:
log22 = 1, log23 = 13, log25 = 16
4. Обчислення log212.
k = 3: 12 * 23 (mod 19) \xF0BA 1 – не представимо у вигляді добутку чисел з S.
k = 7: 12 * 27 (mod 19) \xF0BA 16 = 24.
log212 + 7 \xF0BA 4log22 (mod 18), log212 \xF0BA (4log22 – 7) (mod 18) = 15.
Відповідь: log212 = 15.
Алгоритм Поліга – Хелмана
Якщо така рівність знайдена, то записати рівняння:
(mod n)
2.3. Повторювати кроки 2.1. та 2.2. поки не отримаємо t + c лінійних рівнянь. Невелике ціле число c (1 \xF0A3 c \xF0A3 10) обирається таким чином, щоб складена система рівнянь мала єдиний розв’язок з великою ймовірністю (якщо скласти лише t рівнянь з t невідомими, то з великою ймовірністю два з цих рівнянь будуть залежними і тоді система буде мати більше одного розв’язку).
3. Розв’язати утворену систему рівнянь, отримати значення logapi, 1\xF0A3 i \xF0A3 t.
4. Обчислення logab.
4.1. Обрати деяке ціле k, 0 \xF0A3\xF020k \xF0A3\xF020n - 1 та обчислити b * ak .
4.2. Спробувати представити значення b * ak у вигляді добутку чисел з S:
, di \xF0B3\xF0200
Якщо такого представлення знайти не вдається, виконати знову 4.1. Інакше прологарифмірувавши останню рівність, отримаємо:
- k) mod n
Приклад. Обчислити log212 в групі Z19*.
1. Нехай S = {2, 3, 5} – множникова основа.
2. Будуємо систему рівнянь для знаходження значень log2pi, де pi \xF0CE\xF020S. Оскільки множина S містить 3 елементи, то достатньо отримати 3 лінійно незалежні рівняння.
k = 5: 25 (mod 19) \xF0BA 13 – не представимо у вигляді добутку чисел з S.
k = 7: 27 (mod 19) \xF0BA 14 – не представимо у вигляді добутку чисел з S.
k = 2: 22 (mod 19) \xF0BA 4 = 22. Перше рівняння: 2 = 2log22.
k = 10: 210 (mod 19) \xF0BA 17 – не представимо у вигляді добутку чисел з S.
k = 15: 215 (mod 19) \xF0BA 12 = 22 * 3. Друге рівняння: 15 = 2log22 + log23.
k = 11: 211 (mod 19) \xF0BA 15 = 3 * 5. Третє рівняння: 11 = log23 + log25.
3. Система рівнянь за модулем 18 (порядок Z19* дорівнює 18) має вигляд:
Її розв’язком буде:
log22 = 1, log23 = 13, log25 = 16
4. Обчислення log212.
k = 3: 12 * 23 (mod 19) \xF0BA 1 – не представимо у вигляді добутку чисел з S.
k = 7: 12 * 27 (mod 19) \xF0BA 16 = 24.
log212 + 7 \xF0BA 4log22 (mod 18), log212 \xF0BA (4log22 – 7) (mod 18) = 15.
Відповідь: log212 = 15.
Алгоритм Поліга – Хелмана
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021