Зворотний зв'язок

Дискретний логарифм

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

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

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

ak = , ci 0

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

k = (mod n)

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

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

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

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

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

b * ak = , di 0

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

x = logab = ( - k) mod n

Приклад. Обчислити log212 в групі Z19*.

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

2. Будуємо систему рівнянь для знаходження значень log2pi, де pi S. Оскільки множина S містить 3 елементи, то достатньо отримати 3 лінійно незалежні рівняння.

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

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

k = 2: 22 (mod 19)  4 = 22. Перше рівняння: 2 = 2log22.

k = 10: 210 (mod 19)  17 – не представимо у вигляді добутку чисел з S.k = 15: 215 (mod 19)  12 = 22 * 3. Друге рівняння: 15 = 2log22 + log23.

k = 11: 211 (mod 19)  15 = 3 * 5. Третє рівняння: 11 = log23 + log25.

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

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


Реферати!

У нас ви зможете знайти і ознайомитися з рефератами на будь-яку тему.







Не знайшли потрібний реферат ?

Замовте написання реферату на потрібну Вам тему

Замовити реферат