ค่าสูงสุดสำหรับ N ในปัญหาลอการิทึมแบบไม่ต่อเนื่องคือเท่าใด

ฉันมีรหัสซึ่งสามารถถอดรหัสปัญหาลอการิทึมแบบไม่ต่อเนื่องในเวลา ~ O (0.5n) อย่างไรก็ตาม วิธีนี้ใช้ได้เฉพาะเมื่อ N มีค่าน้อยกว่า P ดังนี้

G^N (สมัย P) เพื่อให้ชัดเจน โปรแกรมของฉันสามารถหาค่าของ N ตาม G และ P ตราบใดที่ N อยู่ระหว่าง 1 ถึง P (รวมและพิเศษตามลำดับ)

สิ่งนี้จะเป็นประโยชน์สำหรับการถอดรหัสบางอย่างเช่น Diffie-Hellman แต่ฉันมีคำถามหนึ่งข้อ: ในปัญหาลอการิทึมที่ไม่ต่อเนื่องส่วนใหญ่เช่นนี้ เป็นเรื่องปกติหรือไม่ที่จะเลือกเฉพาะค่าของ N ระหว่าง 1 และ P

นอกจากนี้ ฉันไม่แน่ใจว่านี่เป็นฟอรัมที่ถูกต้องสำหรับสิ่งนี้หรือไม่ โปรดแจ้งให้ฉันทราบหากไม่เป็นเช่นนั้น

ปัญหาของการแก้ปัญหาสำหรับ $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)$.

¹ เรากำหนด เดอะ ช่วงเวลาเป็นช่วงเวลาบวกต่ำสุดอย่างเคร่งครัด