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

11.3.3 Логарифмирование в полях простого порядка

В этом подразделе мы считаем, что $ n=1$, т. e. будем рассматривать дискретное логарифмирование в группе $ GF(p)*$, где $ p$ -- простое число. Для удобства мы будем работать с полем вычетов $ \mathbb{Z}_p$ по модулю $ p$ и с его мультипликативной группой $ \mathbb{Z}_p*$.

В работе Коямы [Koy] приведены результаты о логарифмировании в $ \mathbb{Z}_p*$, которые означают следующее:     1. Сложность решения уравнения $ a^x=b$, где $ a,b\in\mathbb{Z}_p*$, не зависит от $ a$ и $ b$.

    2. Решить систему уравнений

$\displaystyle \left\{\begin{aligned}
a_1^{\vphantom{X}x}=b_1\\
a_2^x=b_2
\end{aligned}\right.
$

не легче, чем одно уравнение $ a^x=b$ ( $ a,a_1,a_2,b,b_1,b_2\in\mathbb{Z}_p*$).

Положим $ L(p)=e^{\sqrt{\ln p\,\ln\ln p}}$. Следующий алгоритм приводится в виде схемы, не претендующей на подробное описание:

    1. Разложить $ p-1$ на простые множители (с помощью одного из алгоритмов факторизации целых чисел): $ p-1=\prod\limits_{r\in\rho}r^{e_r}$, где $ \rho$ -- конечное множество простых чисел, а $ e_r\geqslant1$.

    2. Выбрать границу гладкости $ L_{1}=[L(p)^{c}]$ (где $ c$ -- некоторая константа) и найти множество $ \pi$ всех простых чисел, не превосходящих $ L_{1}$ (множество $ \pi$ называется факторной базой).

    3. Случайно перебирая целые числа $ t$, $ 1\leqslant
t\leqslant p-2$, выбрать те, для которых либо $ a^t\bmod p$, либо $ ba^t\bmod p$ является гладким по отношению к границе гладкости $ L_{1}$, т. е.

$\displaystyle a^t$ $\displaystyle \equiv\prod_{s\in\pi}s^{\alpha_s(t)}\mkern5mu({\rm mod}\,\,p),$   где $\displaystyle \alpha_s(t)\geqslant0,$ (2)

или


$\displaystyle ba^t$ $\displaystyle \equiv\prod_{s\in\pi}s^{\beta_s(t)}\mkern5mu({\rm mod}\,\,p),$   где $\displaystyle \beta_s(t)\geqslant0.$ (3)

    4. Пусть на предыдущем этапе найдены $ I$ гладких чисел $ a^{u_i}\bmod p$, $ i=1,\ldots,I$, и $ J$ гладких чисел $ ba^{v_j}\bmod p$, $ j=1,\ldots,J$. Построить векторы показателей

$\displaystyle \overline\alpha_i$ $\displaystyle =(\alpha_s(u_i)\bmod(p-1))_{s\in\pi}$   для $\displaystyle i=1,\ldots,I$    

и


$\displaystyle \overline\beta_j$ $\displaystyle =(\beta_s(v_j)\bmod(p-1))_{s\in\pi}$   для $\displaystyle j=1,\ldots,J.$    

Отметим, что если через $ \overline\lambda$ обозначить вектор $ (\log s)_{s\in\pi}$, то, логарифмируя соотношения (2) и (3), можно получить, что

$\displaystyle u_i$ $\displaystyle \equiv\left(\overline\alpha_i,\overline\lambda\right) \mkern5mu({\rm mod}\,\,p-1)$   для $\displaystyle i=1,\ldots,I$ (4)

и


$\displaystyle \log b+v_j$ $\displaystyle \equiv\left(\overline\beta_j, \overline\lambda\right)\mkern5mu({\rm mod}\,\,p-1)$   для $\displaystyle j=1,\ldots,J,$ (5)

где $ (\cdot,\cdot)$ обозначает скалярное произведение по модулю $ p-1$:

$\displaystyle ((x_s)_{s\in\pi},(y_s)_{s\in\pi})=\sum_{s\in\pi}x_sy_s\bmod(p-1).
$

    5. Для каждого $ r\in\rho$ выразить один из векторов $ \overline\beta_j\bmod r^{e_r}$ через векторы $ \overline\alpha_i\bmod r^{e_r}$. Для того, чтобы это было возможно, $ J$ должно быть достаточно велико.

    6. Пусть на предыдущем этапе найдено соотношение $ \overline\beta_j\equiv\sum\limits_{i=1}^{I}\gamma_i
\overline\alpha_i\mkern5mu({\rm mod}\,\,r^{e_r})$, где $ \gamma_i\in\mathbb{Z}_{r^{e_r}}$. Тогда из  (4) и (5) следует, что

$\displaystyle \log b\equiv-v_j+\left(\overline\beta_j,\overline\lambda\right)
\...
...bda\right)\equiv-v_j+\sum_{i=1}^{I}\gamma_i
u_i\mkern5mu({\rm mod}\,\,r^{e_r})
$

и, следовательно, мы можем найти $ (\log b)\bmod r^{e_r}$.

    7. Вычислив $ (\log b)\bmod r^{e_r}$ для всех $ r\in\rho$, с помощью китайской теоремы об остатках найти $ (\log b)\bmod(p-1)$.

Приведенный алгоритм описан в работе Адлемана [Adl], но основные идеи этого алгоритма были изложены в работе Вестерна и Миллера [WM] в 1968 г. В [Adl] получена эвристическая оценка $ O(L(p)^{c_{1}})$ его сложности при условии использования одного из субэкспоненциальных алгоритмов для факторизации $ p-1$. В этой работе рассмотрен и случай, когда $ a$ не является порождающим $ \mathbb{Z}_p*$, т. е. логарифмирование производится в подгруппе группы $ \mathbb{Z}_p*$. Также замечено, что этот общий случай можно свести к случаю, когда $ a$ является порождающим $ \mathbb{Z}_p*$.

Заметим, что, вообще говоря, факторизация $ p-1$ не является необходимой. Достаточно найти один гладкий элемент $ ba^v\bmod p$ и пытаться выразить его через произведение степеней гладких элементов $ a^{u_i}\bmod p$, т. е. проводить исключение в показателях сразу по модулю $ p-1$.

На этапе 5 алгоритма приходится решать разреженные системы линейных уравнений в кольцах вычетов $ \mathbb{Z}_m$. В ряде работ (см. [Copp], [COS]) указано, что метод гауссова исключения здесь не является оптимальным. Предлагается использовать, например, алгоритмы Ланцоша [Lanc] или Видемана [Wied] (см. об этом [COS]). В работе [Gord] описан новый метод исключения, предложенный Померансом.

Дальнейшее развитие указанного метода логарифмирования в $ \mathbb{Z}_p*$ получено Копперсмитом, Одлыжко и Шреппелем в работе [COS]. Сложность вычисления дискретного логарифма доведена до $ L(p)^{1+o(1)}$. Согласно [McC90, стр. 66], алгоритм [COS] был реализован на ЭВМ; результат (см. [LaMO]) позволяет предположить, что вычисление логарифма в $ \mathbb{Z}_p*$ на ЭВМ можно проводить за реальное время при $ p$ порядка $ 10^{100}$.


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


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