Score:1

โมเดลกล่องดำของกลุ่มทั่วไปห้าม MSB ของลอการิทึมแยกหรือไม่

ธง ru

แบบจำลองทั่วไปของกล่องดำห้ามการคำนวณลอการิทึมแบบไม่ต่อเนื่องในกลุ่มของคำสั่ง $q=2p+1$ ที่ไหน $p,q$ เป็นจำนวนเฉพาะสุ่มของ $\Omega(\sqrt{p})$ ขั้นตอน (อ้างอิง ลอการิทึมแบบไม่ต่อเนื่องในแบบจำลองกลุ่มทั่วไปนั้นยาก - ทฤษฎีบทโดย Shoup).

โมเดลทั่วไปของกล่องดำยังห้ามไม่ให้ MSB ของลอการิทึมไม่ต่อเนื่อง $\Omega(\sqrt{p})$ หรือเป็นไปได้หรือไม่ที่อัลกอริทึมทั่วไปของกล่องดำสามารถรับ MSB ของลอการิทึมที่ไม่ต่อเนื่องเข้ามาได้ $โพลีล็อก(p)$ ขั้นตอน?

หมายเหตุในการคำนวณลอการิทึมแบบไม่ต่อเนื่องเมื่อคุณรู้ว่า MSB นั้นไม่สำคัญ แต่มีการโต้ตอบ (การแตกแขนงขึ้นอยู่กับ MSB คือ $0$ หรือ $1$) ซึ่งผมไม่แน่ใจว่ารุ่น Black Box ห้าม

poncho avatar
my flag
ที่จริงแล้ว ถ้า $p = 2^k + \epsilon$ การคำนวณ msbit นั้นง่ายมาก (คุณแค่ติดตามค่า $\epsilon$ ที่ dlog คือ $\ge 2^k$ - ถ้าคุณเห็นอย่างอื่น , msbit เป็นศูนย์). คุณต้องจัดโครงสร้างปัญหา 'คำนวณ msbit' เพื่อหลีกเลี่ยงคำตอบเล็กน้อยดังกล่าว
Turbo avatar
ru flag
อา ฉันเข้าใจแล้ว .. ถือว่า $p$ เป็นจำนวนเฉพาะแบบสุ่ม ประเด็นหลักของฉันคือเรามีการแยกสาขาซึ่งไม่ได้อยู่ในโมเดลอัลกอริทึมทั่วไป ดังนั้นอัลกอริทึมของกล่องดำอาจให้เวลาพหุนามของ MSB ได้หรือไม่ ช่องว่างนี้อนุญาตในผลลัพธ์ที่ทราบในโมเดลกล่องดำหรือไม่
Score:1
ธง my

ซึ่งผมไม่แน่ใจว่ารุ่น Black Box ห้าม"

สิ่งที่โมเดลกล่องดำห้ามคือการดำเนินการใดๆ กับองค์ประกอบกลุ่มนอกเหนือจากชุดการดำเนินการเฉพาะ ในกรณีของคุณ การดำเนินการที่อนุญาตจะเป็น:

  • การดำเนินงานกลุ่ม (อพ $A$ และ $B$, กลับ $A \คูณ B$)

  • การดำเนินการผกผันกลุ่ม

  • การเปรียบเทียบองค์ประกอบสองกลุ่มเพื่อความเท่าเทียมกัน

  • msbit oracle ของคุณ (เนื่องจากคุณกำลังขยายโมเดลกล่องดำเพื่อให้มีการดำเนินการนี้)

การดำเนินการอื่นใดกับองค์ประกอบของกลุ่มเป็นสิ่งต้องห้าม

ในทางกลับกัน การดำเนินการใด ๆ ที่ไม่ใช่องค์ประกอบของกลุ่มถือเป็นเกมที่ยุติธรรม ตัวอย่างเช่น msbit oracle ของคุณคืนค่าบิต บิตนี้ไม่ใช่องค์ประกอบกลุ่ม และทำสิ่งต่างๆ เช่น:

 ถ้า (oracle_returned_a_one) {
     ทำเช่นนี้();
 } อื่น {
     ทำอย่างนั้น();
 }

กำลังเล่นได้อย่างสมบูรณ์แบบ

ดังนั้น เว้นแต่ว่าจำนวนเฉพาะจะอยู่เหนือกำลัง 2 เพียงเล็กน้อย นั่นคือ $p = 2^k + \ell$ สำหรับ $2^k / \text{polylog}(p) < \ell < 2^k$ควรชัดเจนว่าคุณสามารถคำนวณบันทึกแบบไม่ต่อเนื่องด้วยจำนวนการสืบค้นแบบพหุนาม (โดยเฉพาะ $k + \text{polylog}(p)$ สอบถาม)

Turbo avatar
ru flag
คำตอบด่วนที่อยู่
Turbo avatar
ru flag
ดังนั้นขอบเขตล่างของกล่องดำที่ DanielS มอบให้จึงไม่ถูกต้องใน เรากำลังแยก $a,k$ ในขั้นตอน $O(q^{1/4})$ และการแตกบิตของ $a,k$ ไม่ได้เป็นส่วนหนึ่งของการดำเนินการกลุ่ม ถูกต้อง? ขอบเขตล่างของกล่องดำใช้กับไม่สามารถรับ $a+km_1$ **โดยตรง** ในขั้น $o(q^{1/2})$ เท่านั้น ถูกต้อง? และไม่ผ่านขั้นตอนขั้นกลางในการแตกบิตของ $a,k$?
Turbo avatar
ru flag
ความคิดเห็นใด ๆ บนความคิดเห็นข้างต้น?
poncho avatar
my flag
@Turbo: ฉันคิดว่า DanielS ใช้ขอบเขตล่างที่พิสูจน์ได้สำหรับกล่องดำเพื่อแสดงว่าการโจมตีปัญหาเฉพาะก็มีขอบเขตล่างที่พิสูจน์ได้ (ในรูปแบบกล่องดำ)
Turbo avatar
ru flag
เทคนิคของเขาแสดงการผูกล็อกแบบไม่ต่อเนื่อง .. หากปัญหาเฉพาะสามารถทำได้ บันทึกแบบแยกจะมี $O(q^{1/4})$ ผูกไว้เป็นผลลัพธ์ของเขานั่นเป็นเหตุผลที่ฉันคิดว่าขอบเขตของเขาไม่ถูกต้องเพราะเราได้รับเลขชี้กำลังบางส่วนและทำอะไรบางอย่าง (คล้ายกับส่วนของบิตที่นี่ (ซึ่งก็คือ MSB) และทำอะไรบางอย่าง)
Turbo avatar
ru flag
ด้วยเหตุผลข้างต้น ฉันคิดว่าเหตุผลของเขาอาจใช้ไม่ได้ คุณช่วยตรวจสอบอีกครั้งได้ไหม

โพสต์คำตอบ

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