แก้ DLOG โดยใช้อัลกอริทึมความน่าจะเป็นสำหรับ DLOG lsb

ฉันคิดว่าทุกอย่างควรเป็นไปได้หากความน่าจะเป็นเป็นอิสระ/ไม่สัมพันธ์กับบิตสูงของลอการิทึมที่ไม่ต่อเนื่อง

พิจารณาออราเคิลอัลกอริทึมประเภท 1 ซึ่งความน่าจะเป็นของความสำเร็จคือประมาณ 1 ในล้าน กำหนดปัญหาลอการิทึมที่ไม่ต่อเนื่อง $y=g^x$ (ที่ให้ไว้ $y$ หา $0\le x<\ell$) เราสามารถตั้งสมมติฐานได้ว่า 4 บิตล่างของ $x$ โดยทำซ้ำ 16 ครั้ง สิ่งนี้จะทำให้ปัญหาของเราเทียบเท่ากับการแก้ปัญหา $y'=g^{[x/16]}$ และบิตของ $[x/16]$ เป็นบิตของ $x$ เลื่อนลง 4 ตามปกติ เราจะกู้คืนลอการิทึมแยกทีละบิตและเลื่อน เพื่อกู้คืนบิตต่ำของ $[x/16]$ เราเลือกไม่กี่ล้านสุ่ม $r$ ในช่วง $[0,\ell-\ell/16]$ และเรียกใช้อัลกอริทึมของเรา $y'g^r$ (ซึ่งมีลอการิทึมไม่ต่อเนื่อง $0\le [x/16]+r<\ell$. เราคาดว่าจะประสบความสำเร็จอย่างน้อยหนึ่งครั้งและขั้นต่ำของ $[x/16]$ จะเป็นบิตที่ส่งคืนโดยอัลกอริทึม XOR ของเราโดยมีบิตที่มีนัยสำคัญน้อยที่สุด $r$. ล้าง; ทำซ้ำ.

ในทำนองเดียวกันสำหรับอัลกอริทึมประเภท 2 ที่มีความน่าจะเป็น เช่น 0.501 เราก็สร้างเหมือนกัน $y'$ และตัวอย่างอีกครั้ง พูด 100 ล้าน $r$. เราได้รับการคาดคะเน 100 ล้านครั้งสำหรับบิตที่มีนัยสำคัญน้อยที่สุดของ $[x/16]$ ซึ่งในจำนวนนี้ถูกต้องประมาณ 50,100,000 ครั้ง และไม่ถูกต้องประมาณ 49,900,000 ครั้ง โอกาสที่จะได้คำทำนายที่ไม่ถูกต้องมากกว่าคำทำนายที่ถูกต้องนั้นมีน้อยมาก ล้าง; ทำซ้ำ.

ในทั้งสองกรณี อินพุตของอัลกอริทึมสมมติจะถูกเลือกอย่างสม่ำเสมอจากองค์ประกอบชุดใหญ่ (ซึ่งครอบคลุมกลุ่มส่วนใหญ่ของเรา) ซึ่งลอการิทึมแบบไม่ต่อเนื่องจะอยู่ในช่วงเวลาใดช่วงหนึ่ง เว้นแต่พลังของอัลกอริทึมของเราจะมุ่งไปที่องค์ประกอบนอกชุดดังกล่าว เราควรจะสามารถกู้คืนลอการิทึมแบบไม่ต่อเนื่องแบบเต็มได้