Изменения

Перейти к: навигация, поиск

Дискретное логарифмирование в группе

17 байт добавлено, 13:48, 1 июля 2010
Нет описания правки
}}
Рассмотрим конечную [[конечная группа|конечную группу]] <tex>G</tex>. Для заданного <tex>a</tex> необходимо найти такое минимальное <tex>n</tex>, что <tex>a^n=e</tex>. <br>
Теперь рассмотрим '''обобщенную задачу поиска порядка''', также называемую '''задачей дискретного логарифмирования''': для заданных <tex>a</tex> и <tex>b</tex> из группы найти такое минимальное <tex>n</tex>, что <tex>a ^ n = b</tex>. <br>
Очевидно, <tex>n < |G| </tex> (следует из принципа Дирихле). Пусть <tex>m = \lceil \sqrt{|G|} \rceil</tex>. Будем искать <tex>n</tex> в виде <tex>xm-y</tex>, где <tex>y \in 0 \dots m - 1</tex> и <tex>x \in 1 \dots m</tex> (такое представление существует и единственно на основании существования и единственности деления с остатком).<br>
Анонимный участник

Навигация