Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Книги
 Обсудить в форуме  Добавить новое сообщение
Next: 4.9. Заключение Up: 4. Алгоритмические проблемы теории Previous: 4.7. Как раскладывают составные Contents: Содержание


4.8. Дискретное логарифмирование

Пусть $ p$ - нечетное простое число. Еще Эйлер знал, что мультипликативная группа кольца $ \ZZ/p\ZZ$ циклична, т.е. существуют такие целые числа $ a$, что сравнение
\begin{displaymath} a^x\equiv b \pmod p \end{displaymath} (22)

разрешимо относительно $ x$ при любом $ b\in\ZZ $, не делящемся на $ p$. Числа $ a$ с этим свойством называются первообразными корнями, и количество их равно $ \ph(p-1) $, где $ \ph $ - функция Эйлера. Целое $ x$, удовлетворяющее сравнению (22), называется индексом или дискретным логарифмом числа $ b$.

В разделе 2 мы описали алгоритм, позволяющий по заданному числу $ x$ достаточно быстро вычислять $a^x\mod{p}$. Обратная же операция - вычисление по заданному $ b$ его дискретного логарифма, вообще говоря, является очень сложной в вычислительном отношении задачей. Именно это свойство дискретного логарифма и используется в его многочисленных криптографических применениях (см. главу 1). Наиболее быстрые (из известных) алгоритмы решения этой задачи, основанные на так называемом методе решета числового поля, требуют выполнения $ \exp(c(\ln p)^{1/3}(\ln\ln p)^{2/3}) $ арифметических операций (см. [25]), где $ c$ - некоторая положительная постоянная. Это сравнимо со сложностью наиболее быстрых алгоритмов разложения чисел на множители. Конечно, указанная оценка сложности получена при условии справедливости ряда достаточно правдоподобных гипотез.

Говоря о сложности задачи дискретного логарифмирования, мы имели в виду ``общий случай''. Ведь и большое целое число легко может быть разложено на простые сомножители, если все эти сомножители не очень велики. Известен алгоритм, позволяющий быстро решать задачу дискретного логарифмирования, если $ p-1$ есть произведение малых простых чисел.

Пусть $ q$ - простое число, делящее $ p-1$. Обозначим $ c\equiv a^{\frac{p-1}{q}}\pmod p$, тогда классы вычетов $ 1,c, c^2,\dots, c^{q-1}$ все различны и образуют полное множество решений уравнения $ x^q=1 $ в поле $ \FF_p=\ZZ/p\ZZ$. Если $ q$ не велико и целое число $ d$ удовлетворяет сравнению $ x^q\equiv1\pmod p$, то показатель $ k$, $ 0\leq k<q$, для которого выполняется $ d\equiv c^k\pmod p$, легко может быть найден, например, с помощью перебора. Именно на этом свойстве основан упомянутый выше алгоритм.

Допустим, что $ p-1=q^kh$, $ (q,h)=1$. Алгоритм последовательно строит целые числа $ u_j$, $ j=0,1,\dots,k$, для которых выполняется сравнение
\begin{displaymath} \left(b^ha^{-hu_j}\right)^{q^{k-j}}\!\equiv1\pmod p. \end{displaymath} (23)

Так как выполняется сравнение $ b^{hq^k}\equiv1\pmod p$, то найдется целое число $ u_0$, для которого $ b^{hq^{q-1}}\equiv c^{u_0}\pmod p$. При таком выборе сравнение (23) с $ j=0$, очевидно, выполняется. Предположим, что найдено число $ u_j$, удовлетворяющее сравнению (23). Тогда определим $ t$ с помощью сравнения
\begin{displaymath} \left(b^ha^{-hu_j}\right)^{q^{k-j-1}}\!\equiv c^t\pmod p, \end{displaymath} (24)

и положим $ u_{j+1}=u_j+tq^j$. Имеют место сравнения
\begin{displaymath} \left(b^ha^{-hu_{j+1}}\right)^{q^{k-j-1}}\!\equiv c^t a^{-thq^{k-1}}\!\equiv1 \pmod p, \end{displaymath} (25)

означающие справедливость (23) при $ j+1$.

При $ j=k$ сравнение (23) означает в силу (22), что $ a^{(x-u_k)h}\equiv\pmod p$. Целое число $ a$ есть первообразный корень по модулю $ p$, поэтому имеем $ (x-u_k)h\equiv0\pmod{p-1}$ и

\begin{displaymath} x\equiv u_k\pmod{q^k}. \end{displaymath}

Если $ p-1=q_1^{k_1}\cdot\ldots\cdot q_s^{k_s}$, где все простые числа $ q_j$ малы, то указанная процедура позволяет найти вычеты $x\mod{q_i^{k_i}}$, $ i=1,\dots,s$, и, с помощью китайской теоремы об остатках, вычет $x\mod{p-1}$, т.е. решить сравнение (22).

В случае обычных логарифмов в поле действительных чисел имеется специальное основание $ e=2{,}171828\dots$, позволяющее достаточно быстро вычислять логарифмы с произвольной точностью. Например, это можно делать с помощью быстро сходящегося ряда
\begin{displaymath} \ln \frac{1+x}{1-x}=2(x+\frac{x^3}{3}+\frac{x^5}{5}+\dots),\ \vert x\vert<1. \end{displaymath} (26)

Логарифмы по произвольному основанию $ с$ могут быть вычислены с помощью тождества
\begin{displaymath} \log_c x= \frac{\ln x}{\ln c}. \end{displaymath} (27)

В случае дискретных логарифмов нет основания, по которому логарифмы вычислялись бы столь же быстро, как натуральные в поле действительных чисел. Вместе с тем, последняя формула, связывающая логарифмы с различными основаниями, остается справедливой и позволяет выбирать основание удобным способом. Единственное условие для этого состоит в том, чтобы логарифм нового основания $ \Log c$ был взаимно прост с $ p-1$. Тогда в формуле (27) возможно деление по модулю $ p-1$. Заметим, что это условие будет выполнено, если и только если $ c$ - первообразный корень. Из расширенной гипотезы Римана следует, что наименьший первообразный корень по модулю $ p$ ограничен величиной $ O(\log^6p)$. Поэтому в дальнейшем для простоты изложения мы будем предполагать, что основание $ a$ в (22) невелико, именно $ a=O(\log^6p)$.

Так как поле $ \FF_p$ неполно, вычисление дискретных логарифмов не может использовать предельный переход и основано на иных принципах. Прежде всего, нужный дискретный логарифм $ \Log b$ вычисляется не сам по себе, а вместе с совокупностью логарифмов ряда других чисел. Заметим, что всякое сравнение вида
\begin{displaymath} q_1^{k_1}\cdot\ldots\cdot q_s^{k_s}\equiv q_1^{m_1}\cdot\ldots\cdot q_s^{m_s}\pmod p, \end{displaymath} (28)

где $ q_i,k_i, m_i\in\ZZ$, приводит к соотношению между логарифмами
\begin{displaymath} (k_1-m_1)\Log q_1+\dots+(k_s-m_s)\Log q_s\equiv0\pmod{p-1}. \end{displaymath} (29)

А если выполняются сравнения

\begin{displaymath}a\equiv q_1^{r_1}\cdot\ldots\cdot q_s^{r_s} \pmod{p-1} \qquad b\equiv q_1^{x_1}\cdot\ldots\cdot q_s^{x_s}\pmod p, \end{displaymath}

то
\begin{displaymath} r_1\Log q_1+\dots+r_s\Log q_s\equiv1\pmod{p-1}, \end{displaymath} (30)

и
\begin{displaymath} \Log b\equiv x_1\Log q_1+\dots+x_s\Log q_s\pmod{p-1}. \end{displaymath} (31)

Имея достаточно много векторов $ k_1,\dots,k_s$, $ m_1,\dots, m_s$ с условием (28), можно найти решение соответствующей системы сравнений (29), (30). Если эта система имеет единственное решение, то им как раз и будет набор логарифмов $ \Log q_1, \dots,\Log q_s$. Затем с помощью (31) можно найти $ \Log b$.

Мы опишем ниже реализацию этой идеи, взятую из работы [18]. Эвристические соображения позволили авторам [18] утверждать, что предложенный ими алгоритм требует $ L^{1+\varepsilon }$, где $ L=\exp(\sqrt{\ln p\cdot\ln\ln p})$, арифметических операций для вычисления $ \Log b$.

Положим

\begin{displaymath}H=\left[\sqrt p\right]+1,\quad J=H^2-q.\end{displaymath}

Тогда $ 0<J<2\sqrt p+1$, и, как легко проверить, для любой пары целых чисел $ c_1,c_2$ выполняется сравнение
\begin{displaymath} (H+c_1)(H+c_2)\equiv J+(c_1+c_2)H+c_1c_2\pmod p. \end{displaymath} (32)

Если числа $ c_i$ не очень велики, скажем $ c_i\leq L^{1/2+\varepsilon }$ при некотором $ \varepsilon>0$, то правая часть сравнения (32) не превосходит $ p^{1/2+\varepsilon /2}$. Можно доказать, что случайно выбранное натуральное число $ x<p^{1/2+\varepsilon /2}$ раскладывается в произведение простых чисел, меньших $ L^{1/2}$, с вероятностью большей, чем $ L^{-1/2-\varepsilon /2}$.

Обозначим через $ S=\{q_1,\dots,q_s\}$ совокупность всех простых чисел $ q<L^{1/2}$, а также всех целых чисел вида $ H+c$ при $ 0<c<L^{1/2+\varepsilon }$. Тогда $ s=O(L^{1/2+\varepsilon })$. Будем теперь перебирать случайным образом числа и для каждой такой пары пытаться разложить на множители соответствующее выражение из правой части (32). Для разложения можно воспользоваться, например, делением на все простые числа, меньшие чем $ L^{1/2}$. Перебрав все $\nfrac{1}{2}\hbox to0pt{$\phantom{\dfrac{1}{2}}$\hss} (L^{1/2+\varepsilon })^2=O(L^{1+2\varepsilon })$ указанных пар $ c_1,c_2$, мы найдем, как это следует из указанных выше вероятностных соображений, не менее
\begin{displaymath} L^{-1/2-\varepsilon /2}\cdot O(L^{1+2\varepsilon })=O(L^{1/2+3\varepsilon /2}) \end{displaymath} (33)

пар, для которых правая часть сравнения (32) полностью раскладывается на простые сомножители, меньшие $ L^{1/2}$. Сравнение (32), таким образом, принимает вид (28). Так строится система уравнений типа (29).

Напомним, что число $ a$, согласно нашему предположению, существенно меньше, чем $ L^{1/2}$. Поэтому оно раскладывается в произведение простых чисел, входящих в множество $ \{q_1,\dots,q_s\}$, и это приводит к сравнению (30).

Заметим, что количество (33) найденных сравнений типа (29) превосходит число $ s$. Следовательно, построенная система неоднородных линейных сравнений относительно $ \Log q_i$ содержит сравнений больше, чем неизвестных. Конечно, множество ее решений может при этом быть бесконечным. Одна из правдоподобных гипотез состоит в том, что система все-таки имеет единственное решение, и, решив ее, можно определить дискретные логарифмы всех чисел $ q_i $. На этом завершается первый этап работы алгоритма из [18].

Как было отмечено, каждое из чисел, стоящих в правой части сравнения (32), не превосходит $ p^{1/2+\varepsilon /2}$. Поэтому оно раскладывается в произведение не более $ O(\ln p) $ простых сомножителей и, следовательно, каждое из сравнений (29) построенной системы содержит лишь $ O(\ln p) $ отличных от нуля коэффициентов. Матрица системы сравнений будет разреженной, что позволяет применять для ее решения специальные методы с меньшей оценкой сложности, чем обычный гауссов метод исключения переменных.

Вместо перебора всех допустимых значений $ c_i$ в [18] предлагается использовать так называемое решето, отбрасывающее все пары этих чисел, для которых правая часть (32) заведомо не раскладывается в произведение малых простых сомножителей. Для каждого $ c_1 $ и каждой малой простой степени $ q'<L^{1/2}$ можно найти все решения $ c_2<L^{1/2}$ линейного сравнения

\begin{displaymath}J+(c_1+c_2)H+c_1c_2\equiv0\pmod{q'}.\end{displaymath}

Организованная правильным образом, эта процедура одновременно отбирает все нужные пары чисел $ c_1,c_2$ и дает разложение на простые сомножители правых частей сравнений (32).

Итак, после первого этапа работы алгоритма в нашем распоряжении оказываются дискретные логарифмы всех чисел из множества $ S$. Второй этап алгоритма сводит поиск дискретного логарифма числа $ b$ к поиску логарифмов некоторого множества чисел $ u$, не превосходящих по величине $ L^2$. Выбирая случайным образом число $ w$ не более $ L^{1/4}$ раз, можно, как показывают вероятностные соображения, найти такое $ w$, что вычет $a^wb\mod{p}$ раскладывается в произведение простых чисел, меньших $ L^2$. Пусть

\begin{displaymath}a^wb\equiv \prod_{i=1}^{s}q_i^{y_i}\prod_{j=1}^{t}u_j^{z_j} \pmod p \end{displaymath}

такое разложение, где $ u_1,\dots,u_t$ - некоторые простые числа с условием $ L^{1/2}<u<L^2$. На поиск этого сравнения потребуется $ O(L^{1/2})$ арифметических операций. В результате вычисление дискретного логарифма числа $ b$ сводится к вычислению $ t$ дискретных логарифмов для чисел $ u_j$, $ 1\leq j\leq t$ среднего размера.

Наконец, на последнем этапе производится вычисление логарифмов всех чисел $ u_j$. Пусть $ u$ - простое число из интервала $ L^{1/2}<u<L^2$. Обозначим

\begin{displaymath}G=\left[\frac{\sqrt p}{u}\right]\!,\quad I=HGu-p.\end{displaymath}

Для любых целых чисел $ c_1,c_2<L^{1/2+\varepsilon }$ выполняется сравнение
\begin{displaymath} (H+c_1)(H+c_2)u\equiv I+(c_1G+c_2H+c_1c_2)u\pmod p. \end{displaymath} (34)

Отметим, что правая часть этого сравнения не превосходит $ p^{1/2}L^{5/2+\varepsilon }$. Просеивая все числа $ c_1,c_2$ из указанного интервала, можно найти такие, что числа $ G+c_2$ и правая часть сравнения (34) состоят из простых сомножителей, не превосходящих $ L^{1/2}$. Тогда сравнение (34) позволяет вычислить $ \Log u$. Вычисление $ \Log b$ при известных уже значениях $ \Log q_i$ требует $ L^{1/2+\varepsilon }$ арифметических операций.

Существуют и другие способы построения соотношений (28). В [23] для этого используются вычисления в полях алгебраических чисел. В качестве множителей в соотношениях типа (28) используются не только простые числа, но и простые идеалы с небольшой нормой.

Задача вычисления дискретных логарифмов может рассматриваться также и в полях $ \FF_{p^n}$, состоящих из $ p^n$ элементов, в мультипликативных группах классов вычетов $ (\ZZ/m\ZZ)^*$, в группах точек эллиптических кривых и вообще в произвольных группах. С литературой по этому вопросу можно ознакомиться по работе [19].

Next: 4.9. Заключение Up: 4. Алгоритмические проблемы теории Previous: 4.7. Как раскладывают составные Contents: Содержание

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