น่าจะเป็นฟังก์ชันแฮชสากลที่อยู่ใกล้ $ax \bmod p \bmod m$ สร้างเอาต์พุตจากอินพุตที่เท่ากับโมดูโล $m$
สำหรับหนึ่งในฟังก์ชันแฮชสากลที่อยู่ใกล้ $f(x) = ax \bmod p \bmod m$ ที่ไหน $p$ เป็นนายกและ $m < p, m>1$ และ $x$ ช่วงมากกว่า $1 \dots p-1$ ความน่าจะเป็นที่ได้รับคืออะไร $x_r \in \{ x | x \bmod p \bmod m = x \bmod m = r\}$, $f(x_r) = s$เหรอ? นั่นคือค้นหา$Pr_{x_r}(f(x_r)=s)$. ความน่าจะเป็นคือเศษส่วนของ$x$เช่นนั้น $x \bmod p \bmod m = x \bmod m= r$ ที่มี $f(x)=s$.
ฉันถามคำถามนี้เมื่อสองสามเดือนก่อนใน Mathematics Stack Exchange และไม่เคยได้รับคำตอบ ง่ายพอ แต่เป็นระดับการวิจัยหรือการวิจัยก่อนหน้านี้เกี่ยวกับคำถามนั้นยากมากที่จะค้นหา ส่วนด้านล่างนี้เป็นเพียงวิธีที่ฉันคิดเกี่ยวกับเรื่องนี้และไม่ควรจริงจังเกินไปในฐานะส่วนหนึ่งของคำถาม อันที่จริงฉันสงสัยว่ามีวิธีที่ง่ายกว่านี้ในการเข้าหามัน
คำถามนี้แตกต่างจากคำถามทั่วไปเกี่ยวกับความน่าจะเป็นของการชนกันในฟังก์ชันแฮชสากลที่อยู่ใกล้เพราะ $a$ คงที่และ $x$ เป็นตัวแปรและเฉพาะ $x$ด้วยโมดูลัสคู่เดียวกันจะถูกพิจารณา คำตอบดูเหมือนจะเป็นคำถามเกี่ยวกับการนับข้อผิดพลาดแบบ off-by-one คำตอบก็แตกต่างกันมากเช่นกัน ตัวอย่างเช่นถ้า$a=1$, $Pr_{x_r}(f(x_r)=s) = \delta_{r,s}$ และถ้า $a = m+3$, $Pr_{x_r}(f(x_r)=s) \approx \frac{1}{m+3} or \frac{2}{m+3}$.
ฉันคิดถึงข้อผิดพลาดในการโพสต์รั้วสามแหล่งในการนับจำนวนวิธีแก้ปัญหา
ประการแรกโดยไม่ต้องใช้ $\mod p$ หรือ $\mod m$, $f(x_r)=s$ เกิดขึ้นในบางช่วงของความยาวเท่านั้น $p$ ซึ่งทำซ้ำทุกๆ $mp$. (โดยเฉพาะ$s = (a \bmod m)(x_r \bmod m) + \lfloor \frac{ax_r}{p} \rfloor p \bmod m$.) ในตอนท้าย (และจุดเริ่มต้น) ของช่วงของ $f(x)$ ก่อนที่จะใช้โมดูลิอาจมีพื้นที่เพิ่มเติมของความยาว $p$เต็มไปด้วยโซลูชันพิเศษ สิ่งนี้ก่อให้เกิดการเบี่ยงเบนจากความสม่ำเสมอตามลำดับของ$\frac{p}{ma}$ การแก้ปัญหา (และความแตกต่างของความน่าจะเป็นตามลำดับ $\frac{1}{a}$).
ประการที่สองใน 'ลำดับที่สูงกว่า' อาจมีสองภูมิภาคที่จุดเริ่มต้นและจุดสิ้นสุดของช่วงของ $f(x_r)$ (อีกครั้งก่อนที่จะใช้โมดูลิ) โดยที่ตัวเลข $(f(x_r)=s)$- พื้นที่ความยาว $p$มีวิธีแก้ไขเพิ่มเติมแต่ละอย่าง (นั่นคือมีเสารั้วเพิ่มเติมตามความยาว$p$.) ด้วยการเพิ่มแต่ละ $mp$วิธีแก้ปัญหาแรกจะย้อนกลับโดย $m(p \bmod a)$. สิ่งนี้ผลิตตามคำสั่งของ$\frac{a}{p \bmod a}$ $mp$ความยาวซึ่งอาจมีวิธีแก้ไขเพิ่มเติม (จำนวน$mp$s เป็นเรื่องเกี่ยวกับ $\frac{a}{p \bmod a}$ และเศษส่วนบางส่วนของพวกมันจะมีวิธีแก้ปัญหาพิเศษ) เพื่อให้มีวิธีแก้ปัญหาเพิ่มเติมในครั้งแรก $ax_r$ ในหรือหลังค่าพหุคูณที่ถูกต้องของ $p$ ต้องน้อยกว่า $p - \lfloor \frac{p}{am} \rfloor am = p \bmod am$. ดังนั้นจำนวนวิธีแก้ปัญหาพิเศษจริงจะมากที่สุด$\lfloor \frac{p \bmod am}{mp \bmod a} \rfloor + 1$ ในตอนท้ายของแต่ละช่วง
ประการที่สามเนื่องจากช่วงเวลามักไม่ใช่จำนวนเต็มดูเหมือนว่าอาจมีข้อผิดพลาดในการโพสต์รั้วคำสั่งซื้อที่สูงขึ้น หากคุณดูลำดับของการคูณจำนวนมากของ$\frac{a}{p \bmod a}$ $mp$s ที่เล็กกว่าช่วงทั้งหมดของ $f(x_r)$ (นั่นคือทวีคูณของ $mp$ ในการสั่งซื้อ $\frac{(p \bmod a)(ap)}{a(mp)} = \frac{p \bmod a}{m}$ ) (ตัวอย่างเช่นจากการขยายเศษส่วนอย่างต่อเนื่องของ $\frac{a}{p \bmod a}$ หรือจากอำนาจ 10) ควรมีข้อผิดพลาดในการโพสต์รั้วที่ขอบของ $[0,a(p-1)]$สำหรับการประมาณแต่ละครั้งในลำดับ ความยาวของขอบเขตขอบที่ข้อผิดพลาดแบบ off-by-one ควรยาวกว่าสำหรับแต่ละคำสั่ง แต่เศษของข้อผิดพลาด off-by-one ควรมีขนาดเล็กลง ดังนั้นข้อผิดพลาดในการโพสต์รั้วควรเกิดขึ้นที่เศษส่วนคงที่ของอัตราส่วนของความยาวของสมาชิกที่อยู่ติดกันของลำดับดังนั้นหากอัตราส่วนระหว่างความแม่นยำไม่แตกต่างกันมากเกินไปค่าเบี่ยงเบนทั้งหมดจากความสม่ำเสมอควรอยู่ที่ประมาณ$\log p$ แนวทางแก้ไข
ซึ่งหมายความว่าค่าเฉลี่ยสูงกว่า $a$ การเบี่ยงเบนจากความสม่ำเสมอควรเป็นไปตามลำดับ $\frac{m\log p}{p}$. ดังนั้นสำหรับการสุ่มเลือก$a$ส่วนเบี่ยงเบนจากการแจกแจงแบบสม่ำเสมอส่วนใหญ่จะอยู่ในลำดับที่สามของข้อผิดพลาดในการโพสต์รั้ว ตั้งแต่$ax \bmod p \bmod m$เป็นเพียงฟังก์ชันแฮชสากลที่อยู่ใกล้ซึ่งไม่น่าจะเป็นปัญหา แต่ฉันกังวลว่าฉันอาจคิดมากเกินไปและอาจมีวิธีที่ง่ายกว่าในการแก้ปัญหา คำถามนี้ได้รับแรงบันดาลใจจากการคำนวณเลขชี้กำลังแบบโมดูลาร์ที่แฮชในรูปแบบที่แฮชของอัลกอริทึมลอการิทึมแบบไม่ต่อเนื่องของ Shor จากเมทริกซ์รวมแทนการคูณด้วยเลขชี้กำลังกำลังสองของฐานตามที่ระบุไว้ที่นี่:https://arxiv.org/abs/1905.10074 และ https://quantumcomputing.stackexchange.com/questions/12354/shors-discrete-logarithm-algorithm-with-a-qft-with-a-small-prime-base/
คำตอบ
แสดงว่า $\mathbb Z_p^*:=\{1,2,\dots,p-1\}$ และ $\mathbb Z_m:=\{0,1,2,\dots,m-1\}$.
ผมถือว่า $p\nmid a$. แล้ว$f(x) = g(h(x))$, ที่ไหน $h:\mathbb Z_p^*\to \mathbb Z_p^*$ เป็น bijection ที่กำหนดโดย $h(x):=ax\bmod p$และ $g:\mathbb Z_p^*\to \mathbb Z_m$ ถูกกำหนดโดย $g(x):=x\bmod m$.
ปล่อย $b:=(p-1)\bmod m$ และ $q:=\left\lfloor\frac{p-1}m\right\rfloor=\frac{p-1-b}m$. ก็เป็นไปตามนั้น$p=qm+b+1$. ปล่อย$B:=\{1,2,\dots,b\}\subset\mathbb Z_m$ และ $I_B:\mathbb Z_m\to\{0,1\}$ เป็นฟังก์ชันตัวบ่งชี้สำหรับชุด $B$.
ตอนนี้สำหรับการให้ $r,s\in \mathbb Z_m$เรามีพื้นที่ตัวอย่าง $$X_r := \{ x\in Z_p^*\mid x\bmod m=r\} = \{ cm+r\mid \delta_{r0}\leq c\leq q-1+I_B(r)+\delta_{r0}\},$$ ที่ไหน $\delta$เป็นKronecker เดลต้า โดยเฉพาะอย่างยิ่งเรามี$|X_r| = q + I_B(r)$. นี่คือตัวส่วนของความน่าจะเป็น$\mathrm{Pr}(f(x_r)=s)$. การหาตัวเศษนั้นยุ่งยากกว่า
การสุ่มตัวอย่างของ $x_r\in X_r$ สอดคล้องกับการสุ่มตัวอย่างจำนวนเต็ม $c\in [ \delta_{r0}, q-1+I_B(r)+\delta_{r0} ]$และการตั้งค่า $x_r=cm+r$.
เรามี $$(1)\qquad 1\leq cm+r\leq p-1.$$ แล้ว $h(x_r) = acm + ar - kp$ สำหรับบางคน $k$ (ขึ้นอยู่กับ $c$) น่าพอใจ $$(2)\qquad 0\leq acm + ar - kp\leq p-1.$$ สุดท้าย $g(h(x_r))=s$ เทียบเท่ากับ $$(3)\qquad ar - kp = s + mt$$ สำหรับจำนวนเต็ม $t$ (อีกครั้งขึ้นอยู่กับ $c$).
(ใน) ความเท่าเทียมกัน (1), (2), (3) กำหนดรูปทรงหลายเหลี่ยมในพื้นที่ 3 มิติของ $(c,k,t)$และตัวเศษของ $\mathrm{Pr}(f(x_r)=s)$เท่ากับจำนวนจุดจำนวนเต็มในรูปทรงหลายเหลี่ยมนี้ ฉันไม่คิดว่าจะมีนิพจน์ง่ายๆสำหรับตัวเลขนี้ในแง่ของพารามิเตอร์ที่กำหนด$p,m,a,r,s$.