Розклад числа на прості множники, Детальна інформація
Розклад числа на прості множники
Тип документу: Реферат
Сторінок: 3
Предмет: Математика
Автор: Олексій
Розмір: 9.2
Скачувань: 1033
Якщо di \xF0B9 d2i (mod n), то це рівняння може бути ефективно розв’язано для обчислення logab.
Алгоритм обчислення дискретного логарифму
Вхід: генератор циклічної групи G з порядком n (n – просте) та елемент b \xF0CE\xF020G.
Вихід: дискретний логарифм x = logab.
x0 \xF0AC\xF0201, c0 \xF0AC\xF0200, d0 \xF0AC\xF0200.
for i \xF0AC 1, 2, ... do
begin
За значеннями xi-1, ci-1, di-1 та x2i-2, c2i-2, d2i-2 обчислити значення xi, ci, di та x2i, c2i, d2i використовуючи формули (1), (2), (3).
if (xi = x2i) then
begin
r \xF0AC\xF020(di - d2i) mod n;
if (r = 0) then return (FALSE); // розв’язку не знайдено
x \xF0AC r -1 (ci - c2i) mod n;
return (x);
end;
end;
.
Алгоритм обчислення дискретного логарифму
Вхід: генератор циклічної групи G з порядком n (n – просте) та елемент b \xF0CE\xF020G.
Вихід: дискретний логарифм x = logab.
x0 \xF0AC\xF0201, c0 \xF0AC\xF0200, d0 \xF0AC\xF0200.
for i \xF0AC 1, 2, ... do
begin
За значеннями xi-1, ci-1, di-1 та x2i-2, c2i-2, d2i-2 обчислити значення xi, ci, di та x2i, c2i, d2i використовуючи формули (1), (2), (3).
if (xi = x2i) then
begin
r \xF0AC\xF020(di - d2i) mod n;
if (r = 0) then return (FALSE); // розв’язку не знайдено
x \xF0AC r -1 (ci - c2i) mod n;
return (x);
end;
end;
.