Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 11.3.3 Логарифмирование в полях простого порядка Вверх: 11.3 Логарифмирование в GF(q)* Назад: 11.3.1 Алгоритм Гельфонда   Содержание   Предметный указатель

11.3.2 Алгоритм Полига -- Хеллмана

Этот алгоритм (см. также [PH], [Акр, упр. 24 к разд. 3.3.1], [Odl], [Kob, гл. 4, $ \mathsection$ 3]) позволяет быстро вычислять дискретные логарифмы в группе $ GF(q)*$, если $ q-1$ гладкое, т. е. все простые делители $ q-1$ невелики.

Пусть $ q-1=\prod\limits_{s\in\pi}s^{\alpha_s}$, где $ \pi$ -- некоторое конечное множество простых чисел, а $ \alpha_s\geqslant1$. Предполагается, что множество $ \pi$ и числа $ \alpha_s$ для каждого $ s\in\pi$ известны (их можно найти перебором). Алгоритм заключается в следующем:     1. (Построение таблиц.) Для каждого $ s\in\pi$ вычислим набор элементов $ r_{s,j}=a^{j(q-1)/s}$, $ j=\{0,1,\ldots,s-1\}$. Отметим, что порядок $ a^{(q-1)/s}$ равен $ s$, поэтому

$\displaystyle r_{s,0},r_{s,1},\ldots,r_{s,s-1}$ (1)

-- все попарно различные корни $ s$-й степени из единицы в группе $ GF(q)*$. Набор (1) называется таблицей корней $ s$-й степени из единицы.

    2. (Вычисление $ (\log b)\bmod s^{\alpha_s}$ для $ s\in\pi$.) Обозначим через $ x$ искомый (пока неизвестный) $ \log b$ -- дискретный логарифм $ b$ по основанию $ a$. Для каждого $ s\in\pi$ пусть $ x\equiv x_0+x_1s+\ldots+x_{\alpha_s-1}s^{\alpha_s-1}\mkern5mu({\rm mod}\,\,s^{\alpha_s})$, где $ 0\leqslant x_i\leqslant s-1$. Будем последовательно искать $ x_0,x_1,\ldots,x_{\alpha_s-1}$ следующим способом:

  2.1. Вычислим $ b^{(q-1)/s}$. Так как $ b=a^x$, где $ x=x_0+ks$, мы получаем, что

$\displaystyle b^{(q-1)/s}=a^{x(q-1)/s}=a^{x_0(q-1)/s}a^{k(q-1)}=a^{x_0(q-1)/s}=r_{s,x_0}. $

Поэтому для вычисления $ x_0$ достаточно сравнить $ b^{(q-1)/s}$ с элементами таблицы (1) и положить $ x_0$ равным тому $ j$, для которого $ b^{(q-1)/s}=r_{s,j}$.

  2.2. Пусть $ x_0,x_1,\ldots,x_{i-1}$ уже найдены. Вычислим

$\displaystyle c=\left(ba^{-\left(x_0+x_1s+\ldots+x_{i-1}s^{i-1}\right)}\right)^{(q-1)/s^{i+1}}. $

Так как $ b=a^x$, где $ x=x_0+x_1s+\ldots+x_{i-1}s^{i-1}+x_is^i+ls^{i+1}$, мы получаем, что

$\displaystyle c=a^{x_i(q-1)/s}a^{l(q-1)}=a^{x_i(q-1)/s}=r_{s,x_i}. $

Поэтому для вычисления $ x_i$ достаточно сравнить элемент $ c$ с элементами таблицы (1) и положить $ x_i$ равным тому $ j$, для которого $ c=r_{s,j}$.

Таким образом, мы находим $ x_0,x_1,\ldots,x_{\alpha_s-1}$ и, следовательно, $ x\bmod s^{\alpha_s}=x_0+x_1s+\ldots+x_{\alpha_s-1}s^{\alpha_s-1}$ для всех $ s\in\pi$.

    3. (Вычисление $ \log b$.) Используя китайскую теорему об остатках, вычислим искомый дискретный логарифм $ x=x\bmod(q-1)$ по $ x\bmod s^{\alpha_s}$ для $ s\in\pi$, найденным на этапе 2 (см., например, [Акр, разд. 2.3.2]).

Отметим, что если все $ s\in\pi$ не превосходят некоторого полинома от $ \log q$, то вышеописанный алгоритм полиномиален от $ \log q$.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 11.3.3 Логарифмирование в полях простого порядка Вверх: 11.3 Логарифмирование в GF(q)* Назад: 11.3.1 Алгоритм Гельфонда   Содержание   Предметный указатель

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100