Score:1

การกู้คืนโซลูชันทางเลือกสำหรับลอการิทึมแยกที่สามารถโจมตีได้โดยใช้ Pohlig-Hellman

ธง in

ในกระบวนการศึกษาลอการิทึมแบบแยกส่วนและวิธีการที่สามารถทำได้ ฉันเห็นอัลกอริทึม Pohlig-Hellman

ต่อมาเมื่อได้ร่วมงานกับ $h = g^x \mod p$ ที่ไหน $p-1$ เป็นไปอย่างราบรื่น การใช้ Pohlig-Hellman ไม่ได้ให้ผลลัพธ์ตามที่คาดไว้ และส่งกลับสิ่งที่ใหญ่กว่าที่คาดไว้มาก ฉันคิดว่านี่เป็นเพราะ Pohlig-Hellman ข้ามคำตอบที่เล็กที่สุดในบางครั้ง

คำถาม:

  1. ฉันจะกู้คืนให้น้อยที่สุดได้อย่างไร $x$ ถูกต้อง?
  2. ฉันมีขนาดใหญ่ขึ้น $x$; สามารถนำมาใช้เพื่อกู้คืนขนาดเล็ก $x'$?
kelalaka avatar
in flag
คุณเห็น [อัลกอริทึม PohligâHellman : อัลกอริทึมทั่วไป](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm#The_general_algorithm)
in flag
@kelalaka ฉันอ่านผ่านแล้ว ดูเหมือนวิธีการใช้อัลกอริทึมทั่วไป ฉันไม่เห็นว่าจะช่วยให้มีวิธีแก้ปัญหาอื่นได้อย่างไร คุณช่วยชี้ให้ฉันเห็นสิ่งที่ฉันควรดูได้ไหม
meshcollider avatar
gb flag
ค่าที่น้อยที่สุดจะเป็น $x \bmod{(p-1)}$ ถ้า $p$ เป็นจำนวนเฉพาะ
et flag
โซลูชันทั้งหมดเป็นส่วนหนึ่งของคลาสสมมูลที่กำหนดโดย $\bmod (p-1)$ ดังนั้น $x' = x \bmod (p-1)$ ที่กล่าวว่า ขั้นตอนสุดท้ายใน PH algo คือการรวมคำตอบในกลุ่มย่อยโดยใช้ทฤษฎีบทส่วนที่เหลือของจีน และคำตอบจะอยู่ในรูปแบบ $x = something \bmod (p-1)$ ดังนั้นคุณจะได้คำตอบที่เล็กที่สุดเสมอ คุณช่วยระบุรายการโซลูชันกลุ่มย่อยต่างๆ ที่คุณรวมเข้ากับ CRT ได้ไหม
in flag
@ user93353 ฉันลงเอยด้วยการแก้ไขจากข้อความของคุณ ขอบคุณ!

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา