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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:35, 11 июня 2017.
TemplateDifinitionIcon.svg Определение « Алгоритм Шенкса »
Алгоритм Шенкса[1] ( также называемый алгоритмом больших и малых шагов) — в теории групп — детерминированный алгоритм дискретного логарифмирования в мультипликативной группе кольца вычетов по модулю простого числа. Алгоритм был предложен Дэниэлем Шенксом в 1972 году.

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

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

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

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

Shanks01.png

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

В рамках алгоритма сначала для некоторого вычисляются значения , , и т. д. Это - так называемые большие шаги:

Shanks02.png

Затем, на второй стадии алгоритма, вычисляются произведения , , и т. д. Это - малые шаги:

Shanks03.png

Как видно из иллюстрации, в определённый момент становится равен какому-нибудь , который мы вычислили на предыдущем шаге. Таким образом,

,

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

.


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

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

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

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

Если представить как , то сложность алгоритма Шенкса будет , где . У простого перебора сложность .


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

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

.

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

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

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

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

Отсюда:

Итого

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

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

в группе порядка , .

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

При получается, что . Итак,

(очевидно, что ).

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

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

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

, поэтому

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

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

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

Теперь, помня о том, что , а , будем вычислять левую часть:

Q = 0 3
Q = 1
Q = 2
Q = 3

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

.

Ссылки

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