Упрощённый вариант Лучшим путём, чтобы разобраться с данным алгоритмом, будет рассмотрение особого случая, в котором p = 2 n + 1 {\displaystyle p=2^{n}+1} .
Нам даны a {\displaystyle a} , p {\displaystyle p} и b {\displaystyle b} , при этом a {\displaystyle a} есть примитивный элемент G F ( p ) {\displaystyle GF(p)} и нужно найти такое x {\displaystyle x} , чтобы удовлетворялось a x ≡ b ( mod p ) {\displaystyle a^{x}\equiv b{\pmod {p}}} .
Принимается, что 0 ≤ x ≤ p − 2 {\displaystyle 0\leq x\leq p-2} , так как x = p − 1 {\displaystyle x=p-1} неотличимо от x = 0 {\displaystyle x=0} , потому что в нашем случае примитивный элемент a {\displaystyle a} по определению имеет степень p − 1 {\displaystyle p-1} , следовательно:
a p − 1 ≡ 1 ≡ a 0 ( mod p ) {\displaystyle a^{p-1}\equiv 1\equiv a^{0}{\pmod {p}}} .Когда p = 2 n + 1 {\displaystyle p=2^{n}+1} , легко определить x {\displaystyle x} двоичным разложением c коэффициентами { q 0 , q 1 , … , q n − 1 } {\displaystyle \{q_{0},q_{1},\dots ,q_{n-1}\}} , например:
x = ∑ i = 0 n − 1 q i 2 i = q 0 + q 1 2 1 + ⋯ + q n − 1 2 n − 1 {\displaystyle x=\sum \limits _{i=0}^{n-1}q_{i}2^{i}=q_{0}+q_{1}2^{1}+\cdots +q_{n-1}2^{n-1}} Самый младший бит q 0 {\displaystyle q_{0}} определяется путём возведения b {\displaystyle b} в степень ( p − 1 ) / 2 = 2 n − 1 {\displaystyle (p-1)/2=2^{n-1}} и применением правила
b ( p − 1 ) / 2 ( mod p ) ≡ { + 1 , q 0 = 0 − 1 , q 0 = 1. {\displaystyle b^{(p-1)/2}{\pmod {p}}\equiv {\begin{cases}+1,&q_{0}=0\\-1,&q_{0}=1.\end{cases}}} Теперь преобразуем известное разложение и введём новую переменную z 1 {\displaystyle z_{1}} :
b ≡ a x ≡ a x 1 + q 0 ( mod p ) ⇒ z 1 ≡ b a − q 0 ≡ a x 1 ( mod p ) {\displaystyle b\equiv a^{x}\equiv a^{x_{1}+q_{0}}{\pmod {p}}\Rightarrow z_{1}\equiv ba^{-q_{0}}\equiv a^{x_{1}}{\pmod {p}}} ,где
x 1 = ∑ i = 1 n − 1 q i 2 i = q 1 2 1 + q 2 2 2 + ⋯ + q n − 1 2 n − 1 {\displaystyle x_{1}=\sum \limits _{i=1}^{n-1}q_{i}2^{i}=q_{1}2^{1}+q_{2}2^{2}+\cdots +q_{n-1}2^{n-1}} Понятно, что x 1 {\displaystyle x_{1}} делится на 4 {\displaystyle 4} при q 1 = 0 {\displaystyle q_{1}=0} , а при q 1 = 1 {\displaystyle q_{1}=1} делится на 2 {\displaystyle 2} , а на 4 {\displaystyle 4} уже нет.
Рассуждая как раньше, получим сравнение :
z 1 ( p − 1 ) / 4 ( mod p ) ≡ { + 1 , q 1 = 0 − 1 , q 1 = 1 , {\displaystyle z_{1}^{(p-1)/4}{\pmod {p}}\equiv {\begin{cases}+1,&q_{1}=0\\-1,&q_{1}=1,\end{cases}}} из которого находим q 1 {\displaystyle q_{1}} .
Оставшиеся биты получаются похожим способом. Напишем общее решение нахождения q i {\displaystyle q_{i}} с новыми обозначениями:
m i = ( p − 1 ) / 2 i + 1 {\displaystyle m_{i}=(p-1)/2^{i+1}} z i ≡ b ⋅ a − q 0 − q 1 2 1 − ⋯ − q i − 1 2 i − 1 ≡ a x i ( mod p ) {\displaystyle z_{i}\equiv b\cdot a^{-q_{0}-q_{1}2^{1}-\dots -q_{i-1}2^{i-1}}\equiv a^{x_{i}}{\pmod {p}}} ,где
x i = ∑ k = i n − 1 q k 2 k {\displaystyle x_{i}=\sum \limits _{k=i}^{n-1}q_{k}2^{k}} .Таким образом, возведение z i {\displaystyle z_{i}} в степень m i {\displaystyle m_{i}} даёт:
z i m i ≡ a ( x i ⋅ m i ) ≡ ( a ( p − 1 ) / 2 ) ( x i / 2 i ) ≡ ( − 1 ) x i / 2 i ≡ ( − 1 ) q i ( mod p ) {\displaystyle z_{i}^{m_{i}}\equiv a^{(x_{i}\cdot m_{i})}\equiv \left(a^{(p-1)/2}\right)^{(x_{i}/2^{i})}\equiv (-1)^{x_{i}/2^{i}}\equiv (-1)^{q_{i}}{\pmod {p}}} .Следовательно:
z i m i ( mod p ) ≡ { + 1 , q i = 0 − 1 , q i = 1 , {\displaystyle z_{i}^{m_{i}}{\pmod {p}}\equiv {\begin{cases}+1,&q_{i}=0\\-1,&q_{i}=1,\end{cases}}} из которого находим q i {\displaystyle q_{i}} .
Найдя все биты, получаем требуемое решение x {\displaystyle x} .[6]
Пример Дано:
a = 3 , b = 11 , p = 17 = 2 4 + 1 {\displaystyle a=3,\;b=11,\;p=17=2^{4}+1} Найти:
x {\displaystyle x} Решение: Получаем p − 1 = 2 4 {\displaystyle p-1=2^{4}} . Следовательно x {\displaystyle x} имеет вид:
x = q 0 + q 1 2 1 + q 2 2 2 + q 3 2 3 {\displaystyle x=q_{0}+q_{1}2^{1}+q_{2}2^{2}+q_{3}2^{3}} Находим q 0 {\displaystyle q_{0}} :
b ( p − 1 ) / 2 ≡ 11 ( 17 − 1 ) / 2 ≡ 11 8 ≡ ( − 6 ) 8 ≡ ( 36 ) 4 ≡ 2 4 ≡ 16 ≡ − 1 ( mod 17 ) ⇒ q 0 = 1 {\displaystyle b^{(p-1)/2}\equiv 11^{(17-1)/2}\equiv 11^{8}\equiv (-6)^{8}\equiv (36)^{4}\equiv 2^{4}\equiv 16\equiv -1{\pmod {17}}\Rightarrow q_{0}=1} Подсчитываем z 1 {\displaystyle z_{1}} и m 1 {\displaystyle m_{1}} :
z 1 ≡ b ⋅ a − q 0 ≡ 11 ⋅ 3 − 1 ≡ 11 ⋅ 6 ≡ 66 ≡ − 2 ( mod 17 ) {\displaystyle z_{1}\equiv b\cdot a^{-q_{0}}\equiv 11\cdot 3^{-1}\equiv 11\cdot 6\equiv 66\equiv -2{\pmod {17}}} m 1 = ( p − 1 ) / 2 1 + 1 = ( 17 − 1 ) / 2 2 = 4 {\displaystyle m_{1}=(p-1)/2^{1+1}=(17-1)/2^{2}=4} Находим q 1 {\displaystyle q_{1}} :
z 1 m 1 ≡ ( − 2 ) 4 ≡ 16 ≡ − 1 ( mod 17 ) ⇒ q 1 = 1 {\displaystyle z_{1}^{m_{1}}\equiv (-2)^{4}\equiv 16\equiv -1{\pmod {17}}\Rightarrow q_{1}=1} Подсчитываем z 2 {\displaystyle z_{2}} и m 2 {\displaystyle m_{2}} :
z 2 ≡ z 1 ⋅ a − q 1 2 1 ≡ ( − 2 ) ⋅ 3 − 2 ≡ ( − 2 ) ⋅ 6 2 ≡ ( − 2 ) ⋅ 36 ≡ ( − 2 ) ⋅ 2 ≡ − 4 ≡ 13 ( mod 17 ) {\displaystyle z_{2}\equiv z_{1}\cdot a^{-q_{1}2^{1}}\equiv (-2)\cdot 3^{-2}\equiv (-2)\cdot 6^{2}\equiv (-2)\cdot 36\equiv (-2)\cdot 2\equiv -4\equiv 13{\pmod {17}}} m 2 = ( p − 1 ) / 2 2 + 1 = ( 17 − 1 ) / 2 3 = 2 {\displaystyle m_{2}=(p-1)/2^{2+1}=(17-1)/2^{3}=2} Находим q 2 {\displaystyle q_{2}} :
z 2 m 2 ≡ 13 2 ≡ ( − 4 ) 2 ≡ 16 ≡ − 1 ( mod 17 ) ⇒ q 2 = 1 {\displaystyle z_{2}^{m_{2}}\equiv 13^{2}\equiv (-4)^{2}\equiv 16\equiv -1{\pmod {17}}\Rightarrow q_{2}=1} Подсчитываем z 3 {\displaystyle z_{3}} и m 3 {\displaystyle m_{3}} :
z 3 ≡ z 2 ⋅ a − q 2 ⋅ 2 2 ≡ 13 ⋅ 3 − 4 ≡ 13 ⋅ 9 − 2 ≡ 13 ⋅ 2 2 ≡ ( − 4 ) ⋅ 4 ≡ − 16 ≡ 1 ( mod 17 ) {\displaystyle z_{3}\equiv z_{2}\cdot a^{-q_{2}\cdot 2^{2}}\equiv 13\cdot 3^{-4}\equiv 13\cdot 9^{-2}\equiv 13\cdot 2^{2}\equiv (-4)\cdot 4\equiv -16\equiv 1{\pmod {17}}} m 3 = ( p − 1 ) / 2 3 + 1 = ( 17 − 1 ) / 2 4 = 1 {\displaystyle m_{3}=(p-1)/2^{3+1}=(17-1)/2^{4}=1} Находим q 3 {\displaystyle q_{3}} :
z 3 m 3 ≡ 1 1 ≡ 1 ( mod 17 ) ⇒ q 3 = 0 {\displaystyle z_{3}^{m_{3}}\equiv 1^{1}\equiv 1{\pmod {17}}\Rightarrow q_{3}=0} Находим искомый x {\displaystyle x} :
x = 1 + 1 ⋅ 2 1 + 1 ⋅ 2 2 + 0 ⋅ 2 3 ≡ 7 {\displaystyle x=1+1\cdot 2^{1}+1\cdot 2^{2}+0\cdot 2^{3}\equiv 7} Ответ: x = 7 {\displaystyle x=7}
Основное описание Шаг 1 (составление таблицы). Составить таблицу значений { r i , j } {\displaystyle \{r_{i,j}\}} , где r i , j = a j ⋅ p − 1 q i , i ∈ { 1 , … , k } , j ∈ { 0 , … , q i − 1 } . {\displaystyle r_{i,j}=a^{j\cdot {\frac {p-1}{q_{i}}}},i\in \{1,\dots ,k\},j\in \{0,\dots ,q_{i}-1\}.} Шаг 2 (вычисление log a b mod q i α i {\displaystyle \log _{a}{b}\;{\bmod {q_{i}^{\alpha _{i}}}}} ). Для i от 1 до k : Пусть x ≡ log a b ≡ x 0 + x 1 q i + . . . + x α i − 1 q i α i − 1 ( mod q i α i ) , {\displaystyle x\equiv \log _{a}{b}\equiv x_{0}+x_{1}q_{i}+...+x_{\alpha _{i}-1}q_{i}^{\alpha _{i}-1}{\pmod {q_{i}^{\alpha _{i}}}},} где 0 ≤ x i ≤ q i − 1 {\displaystyle 0\leq x_{i}\leq q_{i}-1} . Тогда верно сравнение: a x 0 ⋅ p − 1 q i ≡ b p − 1 q i ( mod p ) {\displaystyle a^{x_{0}\cdot {\frac {p-1}{q_{i}}}}\equiv b^{\frac {p-1}{q_{i}}}{\pmod {p}}} С помощью таблицы, составленной на шаге 1, находим x 0 . {\displaystyle x_{0}.} Для j от 0 до α i − 1 {\displaystyle \alpha _{i}-1} Рассматриваем сравнение a x j ⋅ p − 1 q i ≡ ( b a − x 0 − x 1 q i . . . − x j − 1 q i j − 1 ) p − 1 q i j + 1 ( mod p ) {\displaystyle a^{x_{j}\cdot {\frac {p-1}{q_{i}}}}\equiv (ba^{-x_{0}-x_{1}q_{i}...-x_{j-1}q_{i}^{j-1}})^{\frac {p-1}{q_{i}^{j+1}}}{\pmod {p}}} Решение опять же находится по таблице Конец цикла по j Конец цикла по i Шаг 3 (нахождение ответа). Найдя log a b mod q i α i {\displaystyle \log _{a}{b}\;{\bmod {q_{i}^{\alpha _{i}}}}} для всех i , находим log a b mod ( p − 1 ) {\displaystyle \log _{a}{b}\;{\bmod {\;}}(p-1)} по китайской теореме об остатках .[7] Пример Необходимо найти дискретный логарифм 28 {\displaystyle 28} по основанию 2 {\displaystyle 2} в G F ( 37 ) {\displaystyle GF(37)} , другими словами найти x {\displaystyle x} для:
2 x ≡ 28 ( mod 37 ) {\displaystyle 2^{x}\equiv 28{\pmod {37}}} .Находим разложение φ ( 37 ) = 37 − 1 = 36 = 2 2 ⋅ 3 2 {\displaystyle \varphi (37)=37-1=36=2^{2}\cdot 3^{2}} .
Получаем q 1 = 2 , α 1 = 2 , q 2 = 3 , α 2 = 2 {\displaystyle q_{1}=2,\alpha _{1}=2,q_{2}=3,\alpha _{2}=2} .
Составляем таблицу r i j {\displaystyle r_{ij}} :
r 20 ≡ 2 0 ⋅ 37 − 1 2 ≡ 1 ( mod 37 ) {\displaystyle r_{20}\equiv 2^{0\cdot {\frac {37-1}{2}}}\equiv 1{\pmod {37}}} r 21 ≡ 2 1 ⋅ 37 − 1 2 ≡ 2 18 ≡ − 1 ( mod 37 ) {\displaystyle r_{21}\equiv 2^{1\cdot {\frac {37-1}{2}}}\equiv 2^{18}\equiv -1{\pmod {37}}} r 30 ≡ 2 0 ⋅ 37 − 1 3 ≡ 1 ( mod 37 ) {\displaystyle r_{30}\equiv 2^{0\cdot {\frac {37-1}{3}}}\equiv 1{\pmod {37}}} r 31 ≡ 2 1 ⋅ 37 − 1 3 ≡ 2 12 ≡ 26 ( mod 37 ) {\displaystyle r_{31}\equiv 2^{1\cdot {\frac {37-1}{3}}}\equiv 2^{12}\equiv 26{\pmod {37}}} r 32 ≡ 2 2 ⋅ 37 − 1 3 ≡ 2 24 ≡ 10 ( mod 37 ) {\displaystyle r_{32}\equiv 2^{2\cdot {\frac {37-1}{3}}}\equiv 2^{24}\equiv 10{\pmod {37}}} Рассматриваем q 1 = 2 {\displaystyle q_{1}=2} . Для x {\displaystyle x} верно:
x ≡ x 0 + x 1 q 1 ( mod q 1 α i ) ≡ x 0 + x 1 ⋅ 2 ( mod 2 2 ) {\displaystyle x\equiv x_{0}+x_{1}q_{1}{\pmod {q_{1}^{\alpha _{i}}}}\equiv x_{0}+x_{1}\cdot 2{\pmod {2^{2}}}} Находим x 0 {\displaystyle x_{0}} из сравнения:
a x 0 ⋅ p − 1 q 1 ≡ b p − 1 q 1 ( mod p ) ⇒ 2 x 0 ⋅ 37 − 1 2 ≡ 28 37 − 1 2 ≡ 28 18 ≡ 1 ( mod 37 ) {\displaystyle a^{x_{0}\cdot {\frac {p-1}{q_{1}}}}\equiv b^{\frac {p-1}{q_{1}}}{\pmod {p}}\Rightarrow 2^{x_{0}\cdot {\frac {37-1}{2}}}\equiv 28^{\frac {37-1}{2}}\equiv 28^{18}\equiv 1{\pmod {37}}} Из таблицы находим, что при x 0 = 0 {\displaystyle x_{0}=0} верно выше полученное сравнение.
Находим x 1 {\displaystyle x_{1}} из сравнения:
a x 1 ⋅ p − 1 q i ≡ ( b ⋅ a − x 0 ) p − 1 q i 2 ⇒ 2 x 1 ⋅ 37 − 1 2 ≡ ( 28 ⋅ 2 − 0 ) 37 − 1 4 ≡ 28 9 ≡ − 1 ( mod 37 ) {\displaystyle a^{x_{1}\cdot {\frac {p-1}{q_{i}}}}\equiv (b\cdot a^{-x_{0}})^{\frac {p-1}{q_{i}^{2}}}\Rightarrow 2^{x_{1}\cdot {\frac {37-1}{2}}}\equiv (28\cdot 2^{-0})^{\frac {37-1}{4}}\equiv 28^{9}\equiv -1{\pmod {37}}} Из таблицы получаем, что при x 1 = 1 {\displaystyle x_{1}=1} верно выше полученное сравнение. Находим x {\displaystyle x} :
x ≡ 0 + 1 ⋅ 2 ≡ 2 ( mod 4 ) {\displaystyle x\equiv 0+1\cdot 2\equiv 2{\pmod {4}}} Теперь рассматриваем q 2 = 3 {\displaystyle q_{2}=3} . Для x {\displaystyle x} верно:
x ≡ x 0 + x 1 ⋅ 3 ( mod 3 2 ) {\displaystyle x\equiv x_{0}+x_{1}\cdot 3{\pmod {3^{2}}}} По аналогии находим x 0 {\displaystyle x_{0}} и x 1 {\displaystyle x_{1}} :
2 x 0 ⋅ 37 − 1 3 ≡ 28 37 − 1 3 ≡ 28 12 ≡ 26 ( mod 37 ) ⇒ x 0 = 1 {\displaystyle 2^{x_{0}\cdot {\frac {37-1}{3}}}\equiv 28^{\frac {37-1}{3}}\equiv 28^{12}\equiv 26{\pmod {37}}\Rightarrow x_{0}=1} 2 x 1 ⋅ 37 − 1 3 ≡ ( 28 ⋅ 2 − 1 ) 37 − 1 3 2 ≡ 14 4 ≡ 10 ( mod 37 ) ⇒ x 1 = 2 {\displaystyle 2^{x_{1}\cdot {\frac {37-1}{3}}}\equiv (28\cdot 2^{-1})^{\frac {37-1}{3^{2}}}\equiv 14^{4}\equiv 10{\pmod {37}}\Rightarrow x_{1}=2} Получаем x {\displaystyle x} :
x ≡ 1 + 2 ⋅ 3 ≡ 7 ( mod 9 ) {\displaystyle x\equiv 1+2\cdot 3\equiv 7{\pmod {9}}} Получаем систему:
{ x ≡ 2 ( mod 4 ) x ≡ 7 ( mod 9 ) {\displaystyle {\begin{cases}x\equiv 2{\pmod {4}}\\x\equiv 7{\pmod {9}}\\\end{cases}}} Решим систему. Первое сравнение преобразуем в равенство, которое подставляем во второе сравнение:
x = 2 + 4 ⋅ t ⇒ 2 + 4 ⋅ t ≡ 7 ( mod 9 ) ⇒ 4 ⋅ t ≡ 5 ( mod 9 ) ⇒ {\displaystyle x=2+4\cdot t\Rightarrow 2+4\cdot t\equiv 7{\pmod {9}}\Rightarrow 4\cdot t\equiv 5{\pmod {9}}\Rightarrow } t ≡ 5 ⋅ ( 4 ) − 1 ≡ 5 ⋅ ( − 2 ) ≡ − 10 ≡ 8 ( mod 9 ) {\displaystyle t\equiv 5\cdot (4)^{-1}\equiv 5\cdot (-2)\equiv -10\equiv 8{\pmod {9}}} Подставляем найденное t {\displaystyle t} и получаем искомое x {\displaystyle x} :
x ≡ 2 + 4 ⋅ 8 ≡ 34 ( mod 36 ) ≡ 34 ( mod 37 ) {\displaystyle x\equiv 2+4\cdot 8\equiv 34{\pmod {36}}\equiv 34{\pmod {37}}} Ответ: x = 34 {\displaystyle x=34} .[8]
Если известно разложение (2), то сложность алгоритма является
O ( ∑ i = 1 k α i ( log 2 p + q i 1 − r i ( 1 + log 2 q i r i ) ) ) {\displaystyle O\left(\sum \limits _{i=1}^{k}\alpha _{i}\left(\log _{2}{p}+q_{i}^{1-r_{i}}(1+\log _{2}{q_{i}^{r_{i}}})\right)\right)} , где 0 ≤ r i ≤ 1 {\displaystyle 0\leq r_{i}\leq 1} .При этом необходимо O ( log 2 p ∑ i = 1 k ( 1 + p i r i ) ) {\displaystyle O\left(\log _{2}{p}\sum \limits _{i=1}^{k}\left(1+p_{i}^{r_{i}}\right)\right)} бит памяти.[9]
В общем случае сложность алгоритма также можно оценить как
O ( ∑ i = 1 k α i q i + log p ) {\displaystyle O\left(\sum \limits _{i=1}^{k}\alpha _{i}q_{i}+\log {p}\right)} .[10] Если при обработке каждого qi использовать ускоренные методы (например, алгоритм Шенкса ), то общая оценка снизится до
O ( ∑ i = 1 k α i q i + log p ) {\displaystyle O\left(\sum \limits _{i=1}^{k}\alpha _{i}{\sqrt {q_{i}}}+\log {p}\right)} .В указанных оценках подразумевается, что арифметические операции по модулю p выполняются за один шаг. На самом деле это не так — например, сложение по модулю p требует O (log p ) элементарных операций. Но поскольку аналогичные уточнения имеют место для любого алгоритма, данный множитель часто отбрасывается.
Полиномиальная сложность Когда простые множители { q i } i = 1 k {\displaystyle \left\{q_{i}\right\}_{i=1}^{k}} малы, то сложность алгоритма можно оценивать как O ( ( log 2 p ) 2 ) {\displaystyle O\left((\log _{2}p)^{2}\right)} . [11]
Алгоритм имеет полиномиальную сложность в общем виде O ( ( log p ) c 1 ) {\displaystyle O\left((\log p)^{c_{1}}\right)} в случае, когда все простые множители { q i } i = 1 k {\displaystyle \left\{q_{i}\right\}_{i=1}^{k}} не превосходят ( log p ) c 2 {\displaystyle (\log p)^{c_{2}}} , где c 1 , c 2 {\displaystyle c_{1},c_{2}} — положительные постоянные.[1]
Пример Верно для простых p {\displaystyle p} вида p = 2 α + 1 , p = 2 α 1 3 α 2 + 1 {\displaystyle p=2^{\alpha }+1,\;p=2^{\alpha _{1}}3^{\alpha _{2}}+1} .
Экспоненциальная сложность Если имеется простой множитель q i {\displaystyle q_{i}} такой, что q i ≥ p c {\displaystyle q_{i}\geq p^{c}} , где c ≥ 0 {\displaystyle c\geq 0} .[1]