Алгоритм Гельфонда — Шенкса: различия между версиями

м
LintErrors
(Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0)
м (LintErrors)
: <math>\alpha^x = \beta\,.</math>
Алгоритм Гельфонда — Шенкса основан на представлении <math>x</math> в виде <math>x = i\cdot m - j</math>, где <math>m = \left\lfloor \sqrt{n} \right\rfloor + 1</math>, и переборе <math>1 \leq i \leq m</math> и <math>0 \leq j < m</math>. Ограничение на <math>i</math> и <math>j</math> следует из того, что порядок группы не превосходит <math>m</math>, а значит указанные диапазоны достаточны для получения всех возможных <math>x</math> из полуинтервала <math>\left[0; m\right)</math>. Такое представление равносильно равенству
: {{Нумерованная формула|:|<math> \alpha^{im} = \beta \alpha^j\,.</math>|1}}
Алгоритм предварительно вычисляет <math>\alpha^{im}</math> для разных значений <math>i</math> и сохраняет их в [[Структура данных|структуре данных]], позволяющей эффективный поиск, а затем перебирает всевозможные значения <math>j</math> и проверяет, если <math>\beta \alpha^j</math> соответствует какому-то значению <math>i</math>. Таким образом находятся индексы <math>i</math> и <math>j</math>, которые удовлетворяют соотношению '''(1)''' и позволяют вычислить значение <math>x = i\cdot m - j</math>
<ref name="Глухов">{{книга