Vấn đề giải quyết cho $N$ phương trình $G^N\tương đương A\pmod P$ cho các số nguyên đã cho $P$, $G$, $A$ thường được nêu cho số nguyên $N$ với $0<N\le Q$ cho một số $Q<P$.
Chức năng $N\mapsto G^N\bmod P$ là định kỳ. Do đó nếu $N$ là một giải pháp, tập hợp tất cả các giải pháp thu được bằng cách thêm bội số của chu kỳ¹ của hàm đó vào đó $N$. Vì vậy thật vô nghĩa khi xem xét $N$ lớn hơn khoảng thời gian nếu chúng tôi có thể tìm thấy nó, trong trường hợp đó, chúng tôi chọn giới hạn trên cho $P$ bằng khoảng thời gian đó, và đặt tên cho nó $Q$. Trong mọi trường hợp, kể từ khi $G^N\bmod P$ (khi không $0$) thuộc các số nguyên trong $[1,P-1]$, trong đó có $P-1$ yếu tố, khoảng thời gian không thể vượt quá $P-1$, vì thế $Q<P$.
Thời kỳ đó $Q$ là thứ tự của $G$ modulo $P$, đó là số nguyên nhỏ nhất $Q$ với $G^Q\equiv1\pmod P$. Nó phụ thuộc vào $G$. Nó là một ước số của $\lambda(P)$, ở đâu $\lambda$ Là Hàm Carmichael. $\lambda(P)$ Là $P-1$ khi nào $P$ là số nguyên tố, thấp hơn nếu không.
Khi phân tích thừa số của $P$ đã biết (kể cả số nguyên tố $P$), $\lambda(P)$ rất dễ tính toán, và thứ tự của $G$, là ước của $\lambda(P)$, cũng dễ tính toán.
Thực hành tiêu chuẩn trong mật mã là $P$ một số nguyên tố lớn (ví dụ: ít nhất 1024 bit, tức là 309 chữ số thập phân) và $Q$ lệnh của $G$ modulo $P$, do đó $Q$ một ước số của $P-1$. Tùy thuộc vào hệ thống mật mã có thể được $Q=P-1$, hoặc số nguyên tố $Q=(P-1)/2$, hoặc một số nguyên tố lớn nhẹ $Q$ (ví dụ: ít nhất 160 bit, tức là 49 chữ số thập phân) chia $P-1$. Hai cái trước phổ biến trong Diffie-Hellman, cái sau trong chữ ký Schnorr và DSA.
Tùy thuộc vào độ lớn của $P$ và $Q$, các thuật toán tốt nhất mà chúng tôi biết để tìm $N$ là một trong hai
- Pollard's rho, chi phí nào là $\mathcal O(\sqrt Q)$ phép nhân modulo $P$.
- phép tính chỉ số, mà chi phí tăng chậm hơn đáng kể khi $\log (Q)\lesssim\log(P)$.
¹ Chúng tôi xác định các thời kỳ là thời kỳ tích cực thấp nhất.
