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

กำหนดหมายเลข $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$