Problema rezolvării pt $N$ ecuația $G^N\equiv A\pmod P$ pentru numere întregi date $P$, $G$, $A$ este în general declarată pentru întreg $N$ cu $0<N\le Q$ pentru unii $Q<P$.
Functia $N\mapsto G^N\bmod P$ este periodică. Prin urmare, dacă $N$ este o soluție, mulțimea tuturor soluțiilor se obține prin adăugarea unui multiplu al perioadei¹ a acelei funcție la aceea $N$. Prin urmare, este inutil să luăm în considerare $N$ mai mare decât perioada dacă o putem găsi, caz în care alegem limita superioară pt $P$ egal cu acea perioadă și numiți-o $Q$. În orice caz, din moment ce $G^N\bmod P$ (când nu $0$) aparține numerelor întregi în $[1,P-1]$, care are $P-1$ elemente, perioada nu poate depăși $P-1$, prin urmare $Q<P$.
Perioada aceea $Q$ este ordinul de $G$ modulo $P$, acesta este cel mai mic număr întreg $Q$ cu $G^Q\equiv1\pmod P$. Depinde de $G$. Este un divizor al $\lambda(P)$, Unde $\lambda$ este Funcția lui Carmichael. $\lambda(P)$ este $P-1$ când $P$ este prim, mai mic în caz contrar.
Când factorizarea lui $P$ este cunoscut (inclusiv primul $P$), $\lambda(P)$ este ușor de calculat, iar ordinea $G$, fiind un divizor al $\lambda(P)$, este, de asemenea, ușor de calculat.
Practica standard în criptografie sunt $P$ un prim mare (de exemplu, cel puțin 1024 de biți, adică 309 cifre zecimale) și $Q$ ordinul de $G$ modulo $P$, prin urmare $Q$ un divizor al $P-1$. În funcție de criptosistemul care poate fi $Q=P-1$, sau prim $Q=(P-1)/2$, sau un prim ușor mare $Q$ (de exemplu, cel puțin 160 de biți, adică 49 de cifre zecimale) împărțire $P-1$. Primele două sunt comune în Diffie-Hellman, mai târziu în semnătura Schnorr și DSA.
În funcţie de mărimea $P$ și $Q$, cei mai buni algoritmi pe care știm să îi găsim $N$ sunt fie
- rho lui Pollard, care este costul $\mathcal O(\sqrt Q)$ înmulțiri modulare modulo $P$.
- calculul indicelui, care costă crește considerabil mai lent când $\log (Q)\lesssim\log(P)$.
¹ Noi definim cel perioada ca cea mai joasă perioadă strict pozitivă.
