Расчет индекса основан на двух простых идеях:
- Любое целое число можно представить в виде произведения простых чисел.
- Систему линейных уравнений с небольшим числом переменных можно решить с помощью достаточного количества независимых уравнений.
Возьмем, к примеру, циклическую группу $\mathbb{Z}/p$ с $р$ простой и примитивный корень c. Элементы $с^я$ (за $i=0,1,2,...,p-1$) конгруэнтны по модулю p целым числам $1,2,...,p-1$. Эти целые числа могут быть выражены степенями небольшого числа простых чисел. $P_1,...,P_k$ меньше чем $р$. Если мы знаем индекс каждого простого числа, то, поскольку индексы аддитивны по модулю $p-1$, то мы знаем индекс каждого элемента в нашей группе.
Итак, в этом примере переменными являются индексы простых чисел. $P_j$ а уравнения имеют вид $$c^i=\prod_j P_j^{r_j} \leadsto i=\sum_j r_j \operatorname{ind}(P_j).$$ Обратите внимание, что поскольку $с^я$ также попадет в $P_j$, у нас есть достаточно независимых уравнений для решения для всех индексов. Есть надежда, конечно, что нам не нужно будет перебирать все уравнения, но что первые несколько уже содержат все индексы и достаточно линейно независимы. Выбор c важен с точки зрения того, насколько быстро будет достаточно информации для решения линейной системы.
Вы можете обобщить это на более общие группы, но идея останется прежней.
