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

11.3.4 Алгоритм Хеллмана -- Рейнери

Рассмотрим теперь случай, когда $ p$ невелико. Тогда для дискретного логарифмирования в $ GF(q)*$ применим следующий алгоритм (см. [HR], [Kob, гл. 4, $ \mathsection$ 3]).

    1. Поле $ GF(q)$ представим в виде факторкольца $ GF(p)[y]/(f(y))$, где $ f(y)=f$ -- неприводимый многочлен степени $ n$. Поэтому можно считать, что элементы $ GF(q)$ есть многочлены из $ GF(p)[y]$ степени не выше $ n-1$. Элемент $ a_1=a^{(q-1)/(p-1)}\bmod f$ имеет порядок $ p-1$, следовательно, он является порождающим $ GF(p)*$. Зная его, составляем таблицу логарифмов "констант" -- элементов $ GF(p)*$ (логарифмы по основанию $ a$). Так как $ p$ невелико, то это можно сделать эффективно.

    2. Пусть $ B$ -- множество всех неприводимых многочленов из $ GF(p)[y]$ степени не выше $ m$, где $ m$ -- некоторое натуральное число, меньшее $ n$.

    3. Случайно перебирая $ t$, $ 1\leqslant t\leqslant q-2$, находим те из них, для которых

$\displaystyle a^t\bmod f=c_0\prod_{g\in B}g^{\alpha_g(t)}, $

где $ c_0\in GF(p)$ и $ \alpha_g(t)\geqslant0$. (Разложение $ a^t\bmod f$ на множители можно находить, например, с помощью алгоритма Берлекэмпа (см. [Акр, разд. 6.2.4]), эффективного при малых $ p$). Им соответствуют уравнения

$\displaystyle t\equiv\log c_0+\sum_{g\in B}\alpha_g(t)\log g\mkern5mu({\rm mod}\,\,q-1) $

относительно неизвестных $ \log g$.

    4. Получив на предыдущем этапе достаточно много уравнений относительно $ \log g$, $ g\in B$, решаем систему уравнений и находим $ \log g$, $ g\in B$.

    5. Находим $ t$, такое, что

$\displaystyle ba^t\bmod f=c_1\prod_{g\in B}g^{\beta_g}, $

где $ c_1\in GF(p)$ и $ \beta_g\geqslant0$. Тогда искомый дискретный логарифм равен

$\displaystyle \log b=\left(-t+\log c_1+\sum_{g\in B}\beta_g\log g\right)\bmod(q-1). $

Этот алгоритм имеет субэкспоненциальную сложность.

Несколько иную схему логарифмирования в $ GF(q)*$ предложил Эль Гамаль [ElG84], [ElG85], [ElG86]. Оценка сложности алгоритмов Эль Гамаля субэкспоненциальная (при некоторых эвристических допущениях).

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

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