Проблема решения для $N$ уравнение $G^N\экв А\pmod P$ для заданных целых чисел $P$, $G$, $А$ обычно указывается для целых $N$ с $0<N\leQ$ для некоторых $Q<P$.
Функция $N\mapsto G^N\bmod P$ является периодическим. Следовательно, если $N$ является решением, множество всех решений получается добавлением кратного периода¹ этой функции к этому $N$. Так что бессмысленно рассматривать $N$ больше, чем период, если мы можем его найти, и в этом случае мы выбираем верхний предел для $P$ равный этому периоду, и назовите его $Q$. В любом случае, поскольку $G^N\bmod P$ (когда не $0$) принадлежит целым числам в $[1,P-1]$, который имеет $P-1$ элементы, период не может превышать $P-1$, следовательно $Q<P$.
Тот период $Q$ порядок $G$ по модулю $P$, это наименьшее целое $Q$ с $G^Q\equiv1\pmod P$. Это зависит от $G$. это делитель $\лямбда(П)$, куда $\лямбда$ является функция Кармайкла. $\лямбда(П)$ является $P-1$ когда $P$ простое, меньшее в противном случае.
Когда факторизация $P$ известно (в том числе премьер $P$), $\лямбда(П)$ легко вычислить, а порядок $G$, являясь делителем $\лямбда(П)$, также легко вычислить.
Стандартная практика в криптографии $P$ большое простое число (например, не менее 1024 бит, то есть 309 десятичных цифр) и $Q$ получатель чего-то $G$ по модулю $P$, таким образом $Q$ делитель $P-1$. В зависимости от криптосистемы, которая может быть $Q=P-1$, или премьер $Q=(P-1)/2$, или умеренно большое простое число $Q$ (например, не менее 160 бит, то есть 49 десятичных цифр) деление $P-1$. Первые два обычны для Диффи-Хеллмана, последний — для подписи Шнорра и DSA.
В зависимости от величины $P$ и $Q$, лучшие алгоритмы, которые мы знаем, чтобы найти $N$ либо
- Ро Полларда, стоимость которой $\mathcal O(\sqrt Q)$ модульное умножение по модулю $P$.
- исчисление индекса, стоимость которых растет значительно медленнее, когда $\лог (Q)\lesssim\лог(P)$.
¹ Мы определяем в период как низший строго положительный период.
