รับ bit i เมื่อ modulo n

เห็นได้ชัดว่าคำถามมีจุดประสงค์เพื่อค้นหาสิ่งที่ต้องการ: การแสดงบิตของจำนวนเต็ม $a$ เมื่อทำงานโมดูโล $m$. สิ่งนี้ไม่ได้กำหนดไว้อย่างดี เราจะสมมติว่ามันต้องการตัวแทนบิตของจำนวนเต็มแทน $a\bmodm$.

โดยนิยามจำนวนเต็ม $a\bmodm$ เป็นจำนวนเต็ม $r$ กับ $0\le r<m$ และ $a-r$ หลายรายการ $m$. เมื่อไร $a\ge 0$, นี้ $r$ คือส่วนที่เหลือของการแบ่งเงินปันผลแบบยุคลิด $a$ โดยตัวหาร $m$ให้ผลหารผลหารจำนวนเต็ม $คิว$ และส่วนที่เหลือ $r$, ดังนั้น $0\le r<m$ และ $a=m\cdot q+r$.

เพื่อให้ได้การแสดงจำนวนเต็มฐานที่ไม่เป็นลบ $b\ge2$ (กับ $b=2$ สำหรับการแทนค่าบิต) วิธีมาตรฐานคือการหารแบบยุคลิดต่อเนื่องด้วยตัวหาร $ข$ด้วยการปันผลครั้งแรกเป็นจำนวนเต็มที่ไม่เป็นลบดังกล่าว จากนั้นจึงปันผลที่ตามมาด้วยผลหารที่ได้จากการหารแบบยุคลิดก่อนหน้า ทำซ้ำจนกว่าผลหารจะเท่ากับ $0$. เศษที่เหลือที่ตามมาคือตัวเลขที่ต้องการของการเป็นตัวแทน โดยตัวเลขที่มีนัยสำคัญน้อยที่สุดจะได้ก่อน และมักจะเขียนทางด้านขวา

ดังนั้นเมื่อเราต้องการแทนค่าบิตของ $29\bสมัย 143$ก่อนอื่นเราทราบว่า $0\le29<143$, ดังนั้น $29\bmod 143=29$. เราไม่ต้องการอีกต่อไป $143$. เราแค่ต้องการเป็นตัวแทนของ $29$ ในฐาน $2$. พวกเราเขียน

    29 = 2 * 14 + 1
    14 = 2 *  7 + 0
     7 = 2 *  3 + 1
     3 = 2 *  1 + 1
     1 = 2 *  0 + 1

เศษที่ได้รับคือจำนวนเต็มสุดท้ายในแต่ละบรรทัด และให้นิพจน์ฐานสองของ $29$, นั่นคือ 11101โดยคนแรกได้รับทางด้านขวา

บิตที่ดัชนี $i$ จากด้านขวา (เริ่มต้นที่ดัชนี $i=0$, นั่นคือ ${i+1}^\text{th}$ บิต) ของ $a\bmodm$ สามารถรับเป็น $$\left\lfloor\frac{a\bmod m}{2^i}\right\rfloor\bmod2\tag{1}\label{fgrieueq1}$$

วิธีการในคำถามแทนการใช้ $$\left(a\cdot(2^{-1}\bmod m)^i\bmod m\right)\bmod 2$$ ซึ่งกำหนดไว้สำหรับคี่ $m$ เท่านั้น และเมื่อสามารถเขียนใหม่ได้ (โดยมีนามสกุลเป็น$\bmod$สัญกรณ์เพื่อให้ครอบคลุมเศษส่วน) $$\left(\frac ก{2^i}\bmod m\right)\bmod2$$ ซึ่งค่อนข้างคล้ายกับ \eqref{fgrieueq1} แต่ใช้งานไม่ได้อย่างน่าเชื่อถือ $i=0$. ตัวอย่างเช่น มันล้มเหลวทุกครั้ง $i=1$, $m=2^k+1$ กับ $k>1$และคี่ $a$ กับ $0<a<m$. เนื่องจากวิธีการดังกล่าวไม่มีเหตุผลรองรับ จึงไม่ต้องการการพิสูจน์ที่นอกเหนือไปจากตัวอย่างที่โต้แย้ง