Дискретний логарифм, Детальна інформація

e/O

\x2403\x1103\x5884\x6002\x5884\x6102\x0324

\x0094\x6B00\x4664

\x2403\x1103\x5884\x6002\x5884\x6102\x0324\x0094\x6B00\xE264

H*

.

Приклад. Обчислити 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.

Індексний алгоритм

Алгоритм, базований на обчисленні індексів, є найпотужним при обчисленні дискретного логарифму. Необхідно побудувати відносно невелику підмножину S елементів групи G, яка називається множниковою основою. Ця підмножина повинна обиратися таким чином, щоб як можна більша частина елементів G могла бути представлена у вигляді добутку її елементів. При обчисленні значення logab (a – генератор G, b \xF0CE\xF020G) спочатку обчислюються значення логарифмів елементів з S (які заносяться в тимчасову базу даних), а потім на їх основі обчислюється логарифм числа b.

Алгоритм

Вхід: генератор a циклічної групи G порядка n та елемент b \xF0CE\xF020G.

Вихід: дискретний логарифм x = logab.

1. Побудувати множину S – множникову основу. Нехай S = {p1, p2, …, pt}. В якості значень pi можна обрати, наприклад, i - те просте число.

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

2.1. Обрати деяке ціле k, 0 \xF0A3\xF020k \xF0A3\xF020n - 1 та обчислити ak .

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