ปัญหาของการแก้ปัญหาสำหรับ $N$ สมการ $G^N\equiv A\pmod P$ สำหรับจำนวนเต็มที่กำหนด $พี$, $G$, $A$ โดยทั่วไปจะระบุไว้สำหรับจำนวนเต็ม $N$ กับ $0<N\le Q$ สำหรับบางคน $คิว<พี$.
ฟังก์ชั่น $N\mapsto G^N\bmod P$ เป็นช่วงๆ ดังนั้น ถ้า $N$ เป็นคำตอบ เซตของคำตอบทั้งหมดได้มาจากการบวกผลคูณของคาบ¹ ของฟังก์ชันนั้นเข้ากับชุดนั้น $N$. ดังนั้นจึงไม่มีประโยชน์ที่จะพิจารณา $N$ ใหญ่กว่าระยะเวลาหากเราสามารถหาได้ ซึ่งในกรณีนี้เราจะเลือกขีดจำกัดบนสำหรับ $พี$ เท่ากับช่วงเวลานั้นและตั้งชื่อว่า $คิว$. ไม่ว่าในกรณีใดตั้งแต่ $G^N\bmod P$ (เมื่อไม่ $0$) เป็นของจำนวนเต็มใน $[1,P-1]$ซึ่งมี $P-1$ องค์ประกอบระยะเวลาไม่เกิน $P-1$, เพราะฉะนั้น $คิว<พี$.
ช่วงนั้น $คิว$ เป็นคำสั่งของ $G$ โมดูโล $พี$ซึ่งเป็นจำนวนเต็มที่น้อยที่สุด $คิว$ กับ $G^Q\equiv1\pmod P$. ขึ้นอยู่กับ $G$. เป็นตัวหารของ $\แลมบ์ดา(P)$, ที่ไหน $\แลมบ์ดา$ เป็น หน้าที่ของคาร์ไมเคิล. $\แลมบ์ดา(P)$ เป็น $P-1$ เมื่อไร $พี$ เป็นจำนวนเฉพาะ ต่ำกว่าเป็นอย่างอื่น
เมื่อแยกตัวประกอบของ $พี$ เป็นที่รู้จัก (รวมถึงนายก $พี$), $\แลมบ์ดา(P)$ ง่ายต่อการคำนวณและลำดับของ $G$เป็นตัวหารของ $\แลมบ์ดา(P)$นอกจากนี้ยังง่ายต่อการคำนวณ
แนวปฏิบัติมาตรฐานในการเข้ารหัสคือ $พี$ จำนวนเฉพาะขนาดใหญ่ (เช่น อย่างน้อย 1024 บิต นั่นคือ 309 หลักทศนิยม) และ $คิว$ คำสั่งของ $G$ โมดูโล $พี$, ดังนั้น $คิว$ ตัวหารของ $P-1$. ขึ้นอยู่กับ cryptosystem ที่สามารถ $Q=P-1$หรือนายก $Q=(P-1)/2$หรือไพรม์ขนาดใหญ่เล็กน้อย $คิว$ (เช่น อย่างน้อย 160 บิต นั่นคือ 49 หลักทศนิยม) การหาร $P-1$. สองอันแรกพบได้ทั่วไปใน Diffie-Hellman ต่อมาในลายเซ็นของ Schnorr และ DSA
ขึ้นอยู่กับขนาดของ $พี$ และ $คิว$อัลกอริทึมที่ดีที่สุดที่เรารู้จัก $N$ เป็นอย่างใดอย่างหนึ่ง
- โรของพอลลาร์ดซึ่งค่าใช้จ่ายคือ $\mathcal O(\sqrt Q)$ การคูณแบบโมดูลาร์ การคูณแบบโมดูลาร์ $พี$.
- แคลคูลัสดัชนีซึ่งค่าใช้จ่ายจะเติบโตช้าลงอย่างมากเมื่อ $\log (Q)\lesssim\log(P)$.
¹ เรากำหนด เดอะ ช่วงเวลาเป็นช่วงเวลาบวกต่ำสุดอย่างเคร่งครัด