ค่าสุ่ม $\in [1,N-1]$ สามารถนำไปสู่การสุ่มสมาชิกของลำดับที่แน่นอน $x \mapsto x^\alpha \mod N$ ได้หรือไม่

กำหนด (ตัวอย่าง) จำนวนเฉพาะที่แตกต่างกัน $p,q$ กับ $2 พี+1$, และ $4 พี+3$ ไพรม์เช่นกัน (เหมือนกันสำหรับ $คิว$).
อนุญาต $$N = (4 p+3)\cdot (4 q+3)$$ ด้วยประการฉะนี้ $$s_{i+1} = s_i^4 \mod N$$ จะมี $p\cdot q$ องค์ประกอบ (ในกรณีส่วนใหญ่) สำหรับ $s_0 = r^4 \mod N$ สำหรับค่าสุ่มเกือบทั้งหมด $r$.

แล้วแต่จะเลือก $r$ ที่เกี่ยวข้อง $s_0 = r^4 \mod N$ จะ (เกือบทุกครั้ง) เป็นสมาชิกของ 1 ใน 4 ของลำดับความยาวที่ไม่ต่อเนื่องกัน $p \cdot q$.

คำถาม:
$\text{ }\mathrm{ ฉัน }.$ มีวิธีง่าย ๆ ในการตรวจสอบว่ามีการสุ่มหรือไม่ $r$ นำไปสู่สมาชิกของลำดับ $S_1,S_2,S_3,S_4$?
$\mathrm{II}.$ หรือเราสามารถผลิตแบบสุ่ม $r'$ ข้อใดเป็นสมาชิกลำดับเดียวกัน

(ทั้งที่ไม่มีข้อมูลลับรั่วไหล $s_0$ หรืออื่น ๆ $f(ร)$ เปรียบเทียบได้ด้วย)
(การลดให้น้อยกว่า 4 ลำดับที่มีขนาดเท่ากันก็มีประโยชน์เช่นกัน)

รายละเอียดเพิ่มเติม: ถ้าเราทำ $\mathrm{II}.$ เราต้องรับประกันที่เกี่ยวข้องด้วย $s_0$ ไม่ปฏิบัติตามคำสั่งที่ทราบ เช่น. ถ้าเราผลิต $r'$ ด้วยสมาชิกลำดับที่เลือกตายตัว $s_m$ และ $r' = s_m^{4^r} \mod N$ เรามักจะรู้ตำแหน่งที่เกี่ยวข้องกับ $s_m$ สำหรับทุกๆ $r$ $\mapsto s_{m+r+1}$.

กรณีพิเศษ: สำหรับบางคน $r$ ลำดับจะมีเพียง $p,q$ หรือ $1$ ธาตุ. เราไม่สนใจพวกเขาที่นี่ เพื่อไม่ให้เราต้องเลือก $r$ กับ $$r\in[2,N-1] $$ $$r\mod (4 p+3)\not=0 $$ $$ r\mod (4 q+3)\not=0 $$ $$ r \not\in\{r_*^{2p+1} \mod N \}\land r \not\in\{r_*^{2q+1} \mod N \}$$

เดอะ ศัตรู จะสามารถสร้างสมาชิกแบบสุ่มเหล่านั้นได้ที่เครื่องของเขา สุ่มมา 2 อัน $r$ เขาไม่ควรทราบระยะห่างของดัชนีระหว่างความสัมพันธ์ $s_0$ ในลำดับเป้าหมาย ถ้าเขารู้ว่ามันสุ่ม 2 ครั้ง $r$ เขาไม่น่าจะคำนวณสุ่มครั้งที่ 3 ได้ง่ายๆ $r$ (ในกรณีส่วนใหญ่). เลขชี้กำลัง $\alpha = 4$ สามารถแทนที่ด้วยสิ่งเทียบเท่าที่ยากต่อการคำนวณ

ตัวอย่าง: $N= 7849=47 \cdot 167$ จะผลิต $4$ ลำดับที่มีความยาว $451 = 11 \cdot 41$
(บวกกรณีพิเศษของความยาว $11,41,1$)