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

11.3.5 Алгоритм Копперсмита

Д. Копперсмит [Copp] предложил для группы $ GF(2^n)*$ алгоритм логарифмирования с эвристической оценкой сложности

$\displaystyle e^{c(\ln2^n)^{1/3}(\ln\ln2^n)^{2/3}},$   где $\displaystyle c$ -- константа

Дальнейшее обсуждение деталей этого алгоритма и его реализации на ЭВМ проведено в [Odl] (см. также [McC90]). Алгоритм основан на нахождении удобного представления $ GF(2^n)=GF(2)[y]/(f(y))$, где $ f(y)=y^n+g(y)$ -- неприводимый многочлен, причем $ g(y)$ -- многочлен небольшой степени (меньше $ n^{2/3}$). Например, для $ n=127$ можно взять $ g(y)=y+1$. Схема алгоритма заключается в следующем:     1. На первом этапе мы ищем логарифмы тех элементов $ GF(2^n)*$, которые представимы многочленами из $ GF(2)[y]$ небольшой степени. Выбираем параметры $ d$, $ h$, $ k=2^j$. Затем, перебирая многочлены $ u,v\in GF(2)[y]$ степени не выше $ d$, полагаем $ w=y^hu+v$ и вычисляем $ z=w^k\bmod f$. Поскольку $ k$ есть степень двойки, то $ z\equiv y^{hk}u^k+v^k\bmod f$. При удачном выборе $ f$, $ h$, $ k$ степень многочлена $ y^{hk}\bmod f$ будет невелика; здесь преимущество метода Копперсмита заключается в том, что и $ w$ и $ z$ имеют не очень большую степень. Мы накапливаем те пары $ w$, $ z$, которые раскладываются в произведение неприводимых многочленов $ s\in GF(2)[y]$ небольшой степени, а именно, не превосходящей $ c_0n^{1/3}\ln^{2/3}n=c_1$. Множество всех таких неприводимых многочленов мы обозначим через $ B$.

Пусть

$\displaystyle w\bmod f$ $\displaystyle =\prod_{s\in B}s^{\alpha_s},$    
$\displaystyle z$ $\displaystyle =\prod_{s\in B}s^{\beta_s}$    

Тогда имеем соотношение для логарифмов

$\displaystyle \sum_{s\in B}\beta_s\log s\equiv k\sum_{s\in B}\alpha_s\log s\mkern5mu({\rm mod}\,\,(2^n-1)) $

Получив много таких соотношений, находим значения $ \log s$ для $ s\in B$.

    2. На втором этапе для нахождения искомого дискретного логарифма $ \log b$ мы находим путем случайного перебора число $ t$ такое, что $ ba^t\bmod f$ выражается через произведение неприводимых многочленов $ r$ степени не выше $ c_2=\sqrt{nc_1}$ (множество всех таких неприводимых многочленов мы обозначим через $ C$):

$\displaystyle ba^t\bmod f=\prod_{r\in C}r^{\gamma_r}. $

Далее находим логарифмы элементов $ r\in C$ с помощью техники, аналогичной первому этапу. Тогда искомый дискретный логарифм равен

$\displaystyle \log b=\left(-t+\sum_{r\in C}\gamma_r\log r\right)\bmod(2^n-1). $

Алгоритм Копперсмита позволяет эффективно вычислять логарифмы в $ GF(2^k)*$ при $ k<520$; следовательно, эти поля уже неприменимы для схем криптографии, использующих высокую сложность логарифмирования (см. [Odl], [McC90, стр. 69]). При применении суперкомпьютеров и специальных средств, согласно [McC90, стр. 69], реально даже логарифмирование в $ GF(2^k)*$ при $ k<1280$.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 11.4 Логарифмирование в Z_n* Вверх: 11.3 Логарифмирование в GF(q)* Назад: 11.3.4 Алгоритм Хеллмана - Рейнери   Содержание   Предметный указатель

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