Score:1

กลุ่มจำกัดที่มีฟังก์ชันเกณฑ์

ธง de

ฉันกำลังพยายามหาตัวกำเนิดของกลุ่มจำกัดที่พลังของมันแบ่งกลุ่มออกเป็นสองส่วน ตัวอย่างเช่น ดูที่แถวสุดท้ายของตารางที่แสดงกำลังของ 10 ในกลุ่ม Z_19 ป้อนคำอธิบายรูปภาพที่นี่

คุณสามารถแบ่งกลุ่มออกเป็นสองส่วน องค์ประกอบก่อนหน้า "10^7 mod 19" ซึ่งทั้งหมดน้อยกว่า "13" และองค์ประกอบที่มีและหลัง "10^7 mod 19" ที่มีความน่าจะเป็น 1/2 มากกว่า "13" ฉันกำลังพยายามหากลุ่มที่มีโมดูโลของไพรม์ขนาดใหญ่ (ใหญ่ที่สุดเท่าที่จะปลอดภัยสำหรับวัตถุประสงค์ในการเข้ารหัส) และตัวสร้างที่สามารถแบ่งกลุ่มออกเป็นสองส่วนตามที่ฉันอธิบายไว้ก่อนหน้านี้ จะดีกว่าถ้ากลุ่มพบว่าความน่าจะเป็น 1/2 ที่เราพูดถึงก่อนหน้านี้มีค่าใกล้เคียงกับ 1 ฉันไม่สนใจว่าพาร์ติชันจะขึ้นอยู่กับสิ่งที่แตกต่างกันและไม่มากกว่าหรือน้อยกว่า "13" พาร์ติชันใด ๆ ที่สามารถตรวจสอบได้ง่ายจะมีประโยชน์

fgrieu avatar
ng flag
ขออภัย มีหลายสิ่งหลายอย่างที่ไม่ชัดเจน ก่อนอื่น จำเป็นต้องมีกลุ่มการคูณขนาดใหญ่ และถ้าไม่ใช่ คำถามเกี่ยวข้องกับการเข้ารหัสอย่างไร มีข้อกำหนดด้านขนาดสำหรับสองพาร์ติชันหรือไม่ เราเปลี่ยนเกณฑ์การทดสอบได้ไหม $(g^x\bmod p)
Mahsa Bastankhah avatar
de flag
ใช่ ฉันต้องการกลุ่มการคูณขนาดใหญ่เพราะฉันต้องการบันทึกแยกเพื่อให้คำนวณได้ยาก ฉันต้องการทั้งสองพาร์ติชันให้มีขนาด o(n) เกณฑ์การทดสอบสามารถเป็นอะไรก็ได้ที่เป็นไปได้ทางการคำนวณ เกณฑ์การแบ่งพาร์ติชันควรอยู่ในรูปแบบ x
fgrieu avatar
ng flag
ข้อสังเกต อาจเป็นคำใบ้: ดูเหมือนว่าวิธีการดังกล่าวจะให้ประโยชน์ในการเดาว่า $x
Mahsa Bastankhah avatar
de flag
ใช่ แต่ยังไงก็เป็นการคาดเดา ให้ g^x mod p เสมอ คุณสามารถมีการกระจายความน่าจะเป็นบน x ได้ แต่ไม่สำคัญเพราะมันเป็นเพียงการกระจายความน่าจะเป็น
fgrieu avatar
ng flag
เมื่อกำหนด $g^x\bmod p$ สำหรับ $(p,g)$ ที่ใช้ในการเข้ารหัสและ $x$ แบบสุ่ม เรามักจะเดาสิ่งที่น่าสนใจเกี่ยวกับ $x$ ไม่ได้ (นั่นคือบางสิ่งที่มีความน่าจะเป็นและเป็นส่วนเติมเต็ม ทั้งไม่อันตรธาน). ข้อยกเว้นที่พบได้ยากคือ ถ้าลำดับของ $g$ เป็นเลขคู่ เราสามารถบอกค่าความเสมอภาคของ $x$ ได้ และนั่นจะเกิดขึ้นไม่ได้เมื่อลำดับของ $g$ เป็นจำนวนเฉพาะจำนวนมาก ซึ่งเป็นเรื่องปกติ

โพสต์คำตอบ

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