Score:0

ให้ $N$ กับ $d$ ปัจจัยเฉพาะ จำนวนของค่าที่ไม่ซ้ำกัน $x^d \mod N$ สามารถคำนวณเป็น $d>2$ ได้หรือไม่ จำนวนเงินทั้งหมดลดลงในบางจุดหรือไม่?

ธง at

กำหนดหมายเลข $N$ กับ $d$ ปัจจัยสำคัญที่ไม่ซ้ำกัน สามารถจำนวนของค่าที่ไม่ซ้ำกัน $v$ กับ $$v \equiv x^d \mod N$$ $$x\in[0,N-1]$$ $$N = \prod_{i=1}^{d} p_i$$ คำนวณสำหรับ $d>2$? (ไตรมาสที่ 1)
จำนวนเงินทั้งหมดลดลงในบางจุดหรือไม่? (ไตรมาสที่ 2)


เพื่อความเข้าใจง่าย เราถือว่าแต่ละปัจจัยสำคัญ $p_i > 5$.
หรือสำหรับกรณีการใช้งานแต่ละเป้าหมาย $p_i$ ใหญ่พอที่จะหลีกเลี่ยงการแยกตัวประกอบได้ง่าย


การแก้ปัญหาการทดลอง:
สำหรับ $d=1$ มันเป็นเรื่องเล็กน้อย ถ้าเราแทรกทุกค่าจาก $0$ ถึง $N-1$ สำหรับ $x$ ใน $x^1 \mod N$. เรามีอยู่เสมอ $N$ ค่าที่ไม่ซ้ำกัน
ดังนั้น $N_{x^1} = N$

สำหรับ $d=2$ เรามีกลุ่มโต้ตอบสองกลุ่มจาก $p_1$ และ $p_2$ ด้วยขนาด $p_1-1$ และ $p_2-1$ โดยมีตัวประกอบร่วมอย่างน้อย $2$. หากเรารวมเข้าด้วยกัน เราจะได้ขนาดกลุ่ม (โดยส่วนใหญ่)
$$L = \mathrm{lcm}(\frac{p_1-1}{2}-1, \frac{p_2-1}{2}-1)$$ และอีกจำนวนหนึ่ง $L_n$ ตัวอย่าง $$L_n = \mathrm{gcd}(\frac{p_1-1}{2}-1, \frac{p_2-1}{2}-1)$$ และกรณีพิเศษบางประการสำหรับ $0$, $1$, ตัวเลขที่มีเครื่องหมาย '$\frac{p_i-1}{2}$'-th กำลัง ($\mod N$) และกรณีพิเศษพิเศษบางอย่างถ้าเป็นฐานด้วย $p_i^2$
ด้วยสิ่งนี้ เราสามารถคำนวณจำนวนรวมของการตกค้างกำลังสอง ($d=2$) $N_{x^2}$ ท่ามกลาง $\mathbb Z/N\mathbb Z$: $$N_{x^2} = L_n\cdot L + 2 + 2 (\frac{p_1-1}{2}-1)+2(\frac{p_2-1}{2}-1)+2$ $ (รายละเอียดเพิ่มเติมใน คำตอบ และ คำถาม)

ไตรมาสที่ 1: มีสมการทั่วไปมากกว่านี้สำหรับ $d>2$?


การทดสอบรอบ:
ในการทดสอบบางอย่างสำหรับ $d \ใน [2,3,4,5,6]$ ฉันคำนวณค่าที่เป็นไปได้ทั้งหมดและสังเกตอัตราส่วน $$R_d = \frac{N_{x^d}}{N}$$ เป็นไปได้ $1$ สำหรับ $d\in [3,5]$ แต่ยังเป็นเพียง $0.1$. สำหรับ $d=2$ ของมัน $R_2 \ประมาณ 0.25$.
$R_4$ อยู่เสมอ $<0.05$ ในกรณีทดสอบ $R_6$ ดูเหมือนจะเล็กลงด้วย $R_6<0.001$

Q2.1: อัตราส่วนนี้จะลดลงต่อไปหรือไม่หากใหญ่ขึ้น (เท่ากัน) $d$?

คำถามที่ 2.2: คิดเป็นจำนวนเงินทั้งสิ้น $N_{x^d}$ ลดลงบ้าง $d$?
สมมติว่า $N$ ใหญ่ขึ้น 512 บิตสำหรับแต่ละปัจจัยสำคัญใหม่ จะมี $d$ (กับ $d \cdot 512$-นิดหน่อย $N$) ซึ่งมีน้อยกว่า $N_{x^d}$ กว่า $N_{x^2}$ (กับ $2\cdot 512 = 1024$-นิดหน่อย $N$)? (ไตรมาสที่ 2.3)


ตัวอย่าง:
$d=2$
$N = 50471 =41\cdot 1231$ กับ $N_{x^2}=12936$ และ $R_2 = 0.256$
$N = 28363 = 113 \cdot 251$ กับ $N_{x^2}= 7182 $ และ $R_2 = 0.253$

$d=3$
$N =18031=13\cdot 19\cdot 73$ กับ $N_{x^3}=875$ และ $R_3 =0.04$
$N =11339=17\cdot 23\cdot 29$ กับ $N_{x^3}=11339$ และ $R_3 = 1.0$

$d=4$
$N =97867=7\cdot 11\cdot 31\cdot 41$ กับ $N_{x^4}=4224$ และ $R_4=0.04$
$N =63427=7\cdot 13\cdot 17\cdot 41$ กับ $N_{x^4}=880$ และ $R_4=0.01$

$d=5$
$N =3453307=11\cdot 13\cdot 19\cdot 31\cdot 41$ กับ $N_{x^5}=46683$ และ $R_5=0.0135$
$N =1659931=7\cdot 13\cdot 17\cdot 29\cdot 37$ กับ $N_{x^5}=1659931$ และ $R_5=1.0$

$d=6$
$N=28709681=7\cdot 11\cdot 13\cdot 23\cdot 29\cdot 43$ กับ $N_{x^6}=51840$ และ $R_6=0.0018$
$N=35797223=7\cdot 11\cdot 17\cdot 23\cdot 29\cdot 41$ กับ $N_{x^6}=408240$ และ $R_6=0.011$
$N=28527037=7\cdot 11\cdot 17\cdot 19\cdot 31\cdot 37$ กับ $N_{x^6}=18109$ และ $R_6=0.000635$

Score:1
ธง ru
  1. ใช่สำหรับสแควร์ฟรี $N$ สูตรคือ $$\prod_{i=1}^d\left(1+\frac{p_i-1}{(d,p_i-1)}\right)$$

  2. นิพจน์ข้างต้นจะเท่ากับ $N$ ถ้า $(d,p_i-1)=1$ สำหรับทุกอย่าง $i$. สำหรับคี่ $d$ เราสามารถหาจำนวนเฉพาะโดยพลการด้วยคุณสมบัตินี้ มันเป็นไปตามที่สูงสุดของ $R_d$ เป็น 1 สำหรับคี่ $d$ ซึ่งรวมถึงค่าขนาดใหญ่ของ $d$

ในทางกลับกัน สำหรับอะไรก็ตาม $d$ เราสามารถสร้าง $N$ จากจำนวนเฉพาะทั้งหมดเป็น 1 ม็อด $d$. ในแบบที่เราหาได้ $N$ ดังนั้น $R_d(N)=O(d^{-d})$แต่เช่นนั้น $N$ มีความเบาบาง

J. Doe avatar
at flag
น่าสนใจ ฉันคิดว่ามันเป็นสมการที่ซับซ้อนกว่านี้ ขอบคุณที่ตอบอีกครั้ง หมายเหตุเพียงข้อเดียว: $(a,b)$ เป็นคำสั้นๆ ทั่วไปสำหรับ $\mathrm{gcd}(a,b)$ หรือคุณละเว้นด้วยเหตุผลใดก็ตาม
J. Doe avatar
at flag
เกี่ยวข้องกับ Q2.2 มาก ถ้า $N$ เพิ่มขึ้นประมาณ $B$ บิตกับแต่ละปัจจัย เราจะต้องการปัจจัยเฉพาะจำนวนมาก ($2^B$) เพื่อลดจำนวนทั้งหมดซึ่งเป็นไปไม่ได้ (ไม่ใช่จำนวนเฉพาะจำนวนมาก)
Daniel S avatar
ru flag
$(a,b)$ สำหรับตัวหารร่วมมากเป็นสัญกรณ์ทั่วไปในทฤษฎีจำนวน แม้ว่า $\mathrm{gcd}(a,b)$ ที่ชัดเจนกว่ามักจะใช้ในการเข้ารหัส ฉันคิดว่าถ้า $d$ ไม่ใหญ่มากหรือ $B$ เล็กมาก ก็ควรมีจำนวนเฉพาะจำนวนมาก

โพสต์คำตอบ

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