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

. Логарифмуючи останню рівність за основою 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).

8

F

H

`

b

’

”

\x0153

 

c

¤

\x00A8

\x00AA

3/4

A

A