กำหนดวงจร $x\mapsto x^a$ โดยเริ่มต้นที่ $x_0$ สมาชิกรอบอื่น ๆ สามารถสร้าง $x_1,x_2$ โดยไม่รั่วไหล $j$ ใน $x_1=x_2^{a^j}\mod N$ (ไม่ใช่ไพรม์) ได้หรือไม่

สามารถสร้างลำดับวงจรได้ด้วย

$$s_{i+1} = s_i^a \mod N$$ กับ $N = P \cdot Q$ และ $P = 2\cdot p+1$ และ $Q = 2\cdot q+1$ กับ $พี,คิว,พี,คิว$ ช่วงเวลาที่ต่างกัน
และ $a$ รากดั้งเดิมของ $p$ และ $คิว$.

อนุญาต $s_0 = x_0$ เป็นสารตกค้างกำลังสอง $\mod N$ และลำดับวงจร $S = \{x_0^{a^i} \mod N\}$
(เราไม่สนใจฐานกรณีพิเศษเช่น $0,1$ ที่นี่)

คำถาม: ได้อย่างไร(หลอก)-สุ่มสมาชิก $x_r$ ของลำดับเดียวกัน (ไม่ต้องเท่ากับ $S$) ถูกผลิตโดยไม่รั่วไหลของตัวแปรที่เกี่ยวข้องกับความปลอดภัย (เช่น $พี,คิว,พี,คิว$) หรือดัชนีของพวกเขา $i$ ใน $$x_r = s_i = x_0^{a^i} \mod N $$ หรือให้ค่าสุ่มหลายค่า $x_1,x_2$ ระยะห่างของดัชนี $เจ$ ใน $$x_1=x_2^{a^j}\mod N$$

ข้อมูลเพิ่มเติม:

เป็นเลขยกกำลัง $a$ เป็นรากดั้งเดิมของ $p,q$ ความยาว $L_S$ ของลำดับ $S$ คือ (ในกรณีส่วนใหญ่) $$L_S = \mathrm{lcm}(p-1,q-1)$$ จำนวนของลำดับดังกล่าว $N_S$ เป็น $$N_S = \mathrm{gcd}(p-1,q-1)$$ กรณีพิเศษ: สำหรับจุดเริ่มต้นของ $0$ หรือ $1$ ความยาวรอบเพียง 1
หากเรามี $p$กำลัง -th ($\mod N$) รอบจะมีความยาวเพียง $1$ ใน $\mathbb Z/p\mathbb Z$.
รวมกับความยาวรอบสำหรับ $คิว$ เราจะได้ความยาวของ $\mathrm{lcm}(1,q-1) = q-1$
เหมือนกัน $คิว$- พลัง $\mathrm{lcm}(p-1,1) = p-1$
มีอยู่อย่างละ 2 อย่าง ขึ้นอยู่กับว่าเป็นผลคูณของ $P^2 \mod N$ สำหรับ $p$กำลัง -th หรือหลายของ $Q^2$ สำหรับ $คิว$-th-อำนาจ.
สำหรับค่าเริ่มต้น $(P^2)^q,(Q^2)^p \mod N$ เราได้รับความยาวรอบของเท่านั้น $1$ แต่ละอย่างใน $\mathbb Z/p\mathbb Z$ กับ $P^2 \equiv 1 \mod p$ และพลัง $คิว$ เหลือเท่าเดิมค่า.

ด้วยเหตุนี้ เราจึงทราบจำนวนรวมของการตกค้างกำลังสอง $N_{x^2}$ ท่ามกลาง $\mathbb Z/N\mathbb Z$: $$N_{x^2} = 2 + 2 (q-1)+2(p-1)+2+N_S\cdot L_S$$

-------------

การแก้ปัญหาการทดลอง

ในการแก้ปัญหานี้ เราสามารถถ่ายโอนตัวแปรสุ่มจากลำดับสุ่มไปยังลำดับเป้าหมาย หรือจำกัดจำนวนสุ่มของเราไว้ที่สมาชิกของลำดับเป้าหมาย
ในการถ่ายโอนจากลำดับหนึ่ง $s_1$ ไปยังสมาชิกใดๆ ของลำดับอื่น $s_2$ เรากำลังมองหาเลขยกกำลัง $ข$ กับ

$$x_{s_1}^b \equiv x_{s_2}^{a^i} \mod N$$

เรารู้เกี่ยวกับ $b \not = \{a^i \mod (\phi{(N) = (P-1)(Q-1)}\}$. นอกจากรากดั้งเดิม $a$ นั่นเป็นกรณีสำหรับรากดั้งเดิมอื่น ๆ ทั้งหมดจาก $p,q$.
แต่เท่าที่ฉันรู้ว่ามันยากที่จะทดสอบแบบสุ่ม $ข$.
อย่างไรก็ตาม เราทราบดีว่า $พี,คิว$ ไม่สามารถเป็นพลังของรากดั้งเดิมได้ ดังนั้น $ข$ ย่อมเป็นกำลังแก่คนเหล่านั้นได้ $$ b \equiv P^k \mod \phi(N)$$ เราต้องดูแลสิ่งนี้ $k$ เป็น $\not= 1$ (สิ่งนี้จะรั่วไหล $พี$) และทั้งหมด $N_S$ ลำดับได้โดยวนผ่าน
เราสามารถทำได้โดยการตั้งค่า $k$ ถึง

$$ k = 1 + N_S \cdot n $$ กับ $n \in \mathbb{N_+}$ (และ $b \ไม่\ใน \{0,P\}$) (แก้ไข: สิ่งนี้ดูเหมือนจะไม่วนซ้ำทั้งหมด)

แต่เรายังไม่รู้ว่าปัจจุบันของเรา $x_r$ อยู่ในลำดับเป้าหมาย นอกจากนี้ยังอาจใช้เวลานานหาก $N_S$ มีขนาดใหญ่ (ซึ่งน่าจะเป็นกรณีการใช้งาน)

มีความคิดใดที่จะแก้ไขปัญหานั้น?

อีกวิธีหนึ่งที่จะสร้างมูลค่าตาม $x_0$ และซ่อนดัชนีด้วยเลขยกกำลัง $ค$ ชอบ $$c = P^{N_S \cdot n} \cdot a^k \mod \phi(N)$$ และสร้างค่าสุ่ม $x_r$ ที่ลำดับนี้ $$x_r = x_0^{c^r} \mod N$$ ด้วยการสุ่ม $r$ ของทางเลือก เพิ่มขึ้นก็ตาม $r$ โดยหนึ่งจะเลื่อนดัชนีเป็นจำนวนเดียวกันเสมอ หากทราบความแตกต่างของดัชนีสำหรับการสุ่มสองครั้ง $x_{r_1}, x_{r_2}$ มันจะเป็นที่ทราบกันดีสำหรับค่าสุ่มอื่น ๆ ที่ผลิตด้วยวิธีนี้ นี่จะเป็นการคำนวณที่มีราคาแพงโดยไม่ต้องแชร์ $\phi(น)$

มีความคิดใดที่จะแก้ไขปัญหานั้น?

-------

ตัวอย่างตัวเลข:

$N=6313, P=59, Q=107, p=29, q=53$
กับ $N_S = 4$ รอบของความยาว $L_S = 364$
และรวมของ $N_{x^2} = 1620 $ สี่เหลี่ยม

รากเหง้าดั้งเดิมจาก $p$ และ $คิว$ อยากจะเป็น $a=3$

กำลังเปลี่ยนลำดับ $ข$ อาจจะเป็น $$b = P^{1+N_S \cdot 8} \equiv 1103 \mod (\phi(N)=(P-1)(Q-1)=6148 )$$

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

$$b \in [5 , 10 , 11 , 15 , 17, 20 , 22 , 23 , 30 , 33 34 , 35 , 37 , 40 , 43 , 44 , 45 , 46 , 47 , 51,.. ]$$

ถ้าเราจำกัด $ข$ ให้กับเลขชี้กำลังที่ใช้ $N_S = 4$ ครั้งส่งผลให้ตัวแปรเดียวกันเท่านั้น $32$ เหลือ: $$b \ใน [ 30, 423, 476, 666, 871, 1061, 1114, 1507, 1567, 1960, 2013, 2203, 2408, 2598, 2651, 3044, 3104, 3497, 3550, 3740, 3945, 4188, 4581, 4641, 5034, 5087, 5277, 5482, 5672, 5725, 6118]$$

-------

(คำถามนี้ขึ้นอยู่กับคำตอบของ คำถามที่คล้ายกัน )