Алгоритм Шенкса

Определение « Алгоритм Шенкса »

Алгоритм Шенкса^[1] ( также называемый алгоритмом больших и малых шагов) — в теории групп — детерминированный алгоритм дискретного логарифмирования в мультипликативной группе кольца вычетов по модулю простого числа. Алгоритм был предложен Дэниэлем Шенксом в 1972 году.

Принцип работы алгоритма

Пример Принцип работы алгоритма Шенкса

Как указано в соответствующей статье, простейшим методом решения сравнения вида

$\alpha ^{x}=\beta (modN)\,.$

является умножение $\alpha$ друг на друга до тех пор, пока очередное произведение не удовлетворит условию сравнения:

Как можно понять из иллюстрации, в этом случае на решение сравнения потребуется максимум $N$ шагов, где $N$ - порядок группы вычетов. Для ускорения вычисления, собственно, и был разработан алгоритм Шенкса.

В рамках алгоритма сначала для некоторого $k$ вычисляются значения $\alpha^{k}$ , $\alpha^{2k}$ , $\alpha^{3k}$ и т. д. Это - так называемые большие шаги:

Затем, на второй стадии алгоритма, вычисляются произведения $\beta \cdot \alpha$ , $\beta \cdot \alpha ^{2}$ , $\beta \cdot \alpha ^{3}$ и т. д. Это - малые шаги:

Как видно из иллюстрации, в определённый момент $\beta \cdot \alpha ^{t}$ становится равен какому-нибудь $y_{m}$ , который мы вычислили на предыдущем шаге. Таким образом,

$\alpha ^{x}\cdot \alpha ^{t}=y_{m}=\alpha ^{m}k$ ,

откуда при логарифмировании получается, что

$x=mk-t$ .

Оценка сложности

Пример Оценка сложности

Как видно из описания алгоритма, число его шагов есть функция от выбранной величины деления $k$ следующего вида:

$f=k+{\frac {N}{k}}$

Найдём минимум этой функции:

$f'=1-{\frac {N}{k^{2}}}$

$1-{\frac {N}{k^{2}}}=0\implies N=k^{2}\implies k={\sqrt {N}}$

Если представить $N$ как $e^{n}$ , то сложность алгоритма Шенкса будет $L\sim O(e^{n/2})$ , где $n={\text{ln}}N$ . У простого перебора сложность $L\sim O(e^{n})$ .

Пример использования

Для примера попробуем решить следующее сравнение:

$2^{x}=49(mod101)$ .

Примем $k$ равным 10. Это чуть меньше, чем ${\sqrt {101}}$ , и в общем случае лучше увеличивать значение извлечённого корня дополнительно на 1.

$2^{10}=14(mod101)$

Теперь пробежим все значения m от 1 до 10, чтобы покрыть всё пространство кольца вычетов.

m	1	2	3	4	5	6	7	8	9	10
2^10m = 14^m	14	95	17	36	100	87	6	84	65	1

Приступим к выполнению малых шагов:

$49\cdot 2=98(mod101)$

$98\cdot 2=95(mod101)$

Отсюда:

$2^{x}\cdot 2^{2}=2^{20}$

Итого

$2^{x}=2^{18}$

$x=18$

Альтернативное описание алгоритма

Данный метод применим для любой группы при произвольных условиях. Имеется сравнение вида

$b=a^{x}$

в группе $G$ порядка $N$ , $0\leq x<N$ .

Представим искомое число в следующем виде:

$x=Qd+r,{\begin{cases}0\leq r<N\\0\leq Q<N/d\\\end{cases}}$

При $d\approx {\sqrt {N}}$ получается, что $r<Q\sim {\sqrt {N}}$ . Итак,

$b=a^{Qd+r}\to b{(a^{-d})}^{Q}=a^{r}$ (очевидно, что $a^{-d}=a^{N-d}$ ).

Это соотношение является основным для решения задачи.

Пример использования альтернативного описания

Решим сравнение

$5^{x}=3(mod23)$

$d\sim {\sqrt {23}}$ , поэтому $d=5$

Для решения сравнения строим таблицы для левой и правой частей основного соотношения (кроме того, сортируем правую часть).

Первая стадия - стадия предвычисления:

5^r	1	2	4	5	10
r	0	2	4	1	3

Теперь, помня о том, что $b=3$ , а $5^{-d}=5^{17}=15$ , будем вычислять левую часть:

	$b{(a^{-d})}^{Q}$
Q = 0	3
Q = 1	$3\cdot 15=22$
Q = 2	$22\cdot 15=8$
Q = 3	$8\cdot 15=5$

Нашлось соответствие! Отсюда

$x=Qd+r=3\cdot 5+1=16$ .

Ссылки

↑ Алгоритм Шенкса — Википедия https://ru.wikipedia.org/wiki/Алгоритм_Шенкса

[.5B1.5D-1] Алгоритм Шенкса — Википедия https://ru.wikipedia.org/wiki/Алгоритм_Шенкса

[1]