Score:1

มีสูตรทั่วไปสำหรับจำนวนลำดับต่างๆ ที่ผลิตด้วย $x\mapsto x^\alpha \mod N$ หรือไม่

ธง at

ขึ้นอยู่กับ $\alpha,N,x$ ลำดับ $x\mapsto x^\alpha \mod N$ สามารถมีความยาวต่างกันได้ หากองค์ประกอบแรก $x_0$ เริ่มต้นด้วย $x_0 = x_r^\alpha$ สำหรับการสุ่ม $x_r$ ลำดับจะมีขนาดคงที่เกือบตลอดเวลา
เราจะเน้นเฉพาะลำดับที่พบบ่อยที่สุดที่มีขนาดสูงสุดเท่านั้น $N_L$ (สำหรับให้ $\alpha,N$).

แล้วแต่จะเลือก $x_0$ มันสามารถนำไปสู่ลำดับที่แตกต่างกันและไม่ต่อเนื่องกันโดยยังคงมีขนาดลำดับสูงสุดเท่าเดิม


คำถาม: มีสูตรทั่วไปในการคำนวณจำนวนลำดับเหล่านั้นหรือไม่ (สำหรับ $\alpha,N$)?

แก้ไข: คำตอบที่โพสต์และยอมรับไม่ได้ตอบคำถามนี้ แต่มีประโยชน์มาก
คำตอบสำหรับคำถามนี้ยังคงยินดีต้อนรับ (จบการแก้ไข)


ในขณะที่แก้ไขไปรอบ ๆ ฉันพบสูตรบางอย่างสำหรับบางคนแล้ว $N, \อัลฟา$ ด้วยโครงสร้างพิเศษ ความยาวรอบ $\alpha$ โมดูโลปัจจัยสำคัญบางประการของ $\phi(น)$ และปัจจัยของ $\phi(\phi(N))$ ดูเหมือนจะมีผลกระทบต่อการนับนั้น
นอกจากนี้ยังเกี่ยวข้องกับจำนวนของค่าต่างๆ $N_{\alpha}=|\{x^\alpha \bmod N\}|$ และความยาวสูงสุดของลำดับเหล่านั้น $N_L$.

สำหรับ $N_\อัลฟ่า$ มันได้รับคำตอบในอีกข้อหนึ่ง เกลียว. ถ้า $N$ เป็นผลคูณของปัจจัยเฉพาะ: $$N = \prod_{i=1}^n p_i$$ จำนวนของค่าต่างๆ $N_\อัลฟ่า$ อยากจะเป็น $$N_{\alpha} =\prod_{i=1}^n\left(1+\frac{p_i-1}{\mathrm{gcd}(\alpha,p_i-1)}\right)$$ สำหรับ $N_L$ ฉันแค่สร้างสมการบางอย่างที่ใช้ได้ผลสำหรับบางคน $N, \อัลฟา$. ยินดีต้อนรับสูตรทั่วไป
ทั้งสองอย่างรวมกันอาจนำไปสู่การประมาณจำนวนลำดับ

คำถามเสริม: ลำดับเหล่านั้นมีชื่อพิเศษหรือไม่? คุณสมบัตินี้และคุณสมบัติอื่น ๆ อธิบายไว้ที่ใดที่หนึ่ง (ในรูปแบบกะทัดรัด) หรือไม่?


เป้าหมาย $N$ ก็จะมี $2$,$3$ หรือ $4$ ปัจจัยเฉพาะที่ไม่ซ้ำแบบคี่

Score:2
ธง sa

มันคือ ยากมาก และแก้ปัญหาทางคณิตศาสตร์ทั่วไปไม่ได้ บางทีคุณควรเน้นคำถามของคุณไปที่ เฉพาะเจาะจง กรณีต่างๆ และอาจถามที่ mathoverflow แต่ก็มีความเสี่ยงที่อาจถูกเพิกเฉยได้เสมอ เว้นแต่คุณจะสาธิตการวิจัยก่อนหน้านี้และถามคำถามที่ผ่านการพิจารณาอย่างดี

กรณีเฉพาะของ $N$ นายกได้รับการพิจารณาโดย Igor Shparlinski จุดเริ่มต้นที่ดีคือการไล่ตามการอ้างอิงถึงงานของเขา ตามที่ได้อธิบายไว้ในบทคัดย่อของบทความที่ฉันกล่าวถึงด้านล่าง ปัญหานี้เกี่ยวข้องอย่างใกล้ชิดกับปัญหาอื่นๆ และการประยุกต์ใช้ในทฤษฎีจำนวน

Chua และ Shparlinski ในโครงสร้างวัฏจักรของโมดูโลการยกกำลังแบบซ้ำๆ a ไพรม์ วารสารทฤษฎีจำนวนฉบับ 107 (2004) น. 345–356.

ฉันสามารถเข้าถึงสำเนาผ่าน

เอลส์เวียร์ที่นี่

โปรดทราบว่าผลลัพธ์บางอย่างได้มาจากการสันนิษฐานว่า สรุปสมมติฐานของรีมันน์ ซึ่ง Shparlinski และผู้เขียนร่วมของเขาลบออก เพียงอย่างเดียวน่าจะบอกคุณได้ว่าปัญหานี้ยากเพียงใดโดยทั่วไปที่คุณต้องการ ในบทความนั้น จะมีการประมาณช่วงเวลาของความยาวรอบและจำนวนรอบ

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

J. Doe avatar
at flag
ขอบคุณสำหรับข้อมูล & ลิงค์ ปัญหาคือกรณีพิเศษของเป้าหมายที่เป็นไปได้ขึ้นอยู่กับความยาวและจำนวนของลำดับการสร้าง $\alpha,N$ สำหรับคุณสมบัติบางอย่างได้ผล การรวมพวกเขาเข้าด้วยกันไม่ได้ - ฉันเกือบจะแน่ใจว่ามันจะไม่ได้ผลในตอนท้าย ฉันมองหาความชัดเจนเกี่ยวกับเรื่องนี้ เธรดที่ยาวเกินไปรวมถึงสิ่งที่ทำไปแล้วจะถูกเพิกเฉยในกรณีส่วนใหญ่ และในการคำนวณทางคณิตศาสตร์ คุณจะต้องใช้โชคอีกส่วนหนึ่ง คุณจะไม่มีทางรู้ว่ามันแก้ไขไม่ได้/ยากหรือไม่มีคำตอบเลย
J. Doe avatar
at flag
$x^\alpha$ นี้เป็นความพยายามหนึ่งในการแก้ปัญหาทั่วไปที่ฉายค่าสุ่มในโดเมน 3 มิติที่เล็กที่สุดเท่าที่จะเป็นไปได้โดยมีความสัมพันธ์ที่เข้ารหัสระหว่างจุดเหล่านี้ คำถามทั้งหมดที่ทำที่นี่เกี่ยวกับการทดลองแก้ปัญหานี้ พวกเขาเป็นส่วนหนึ่งของหัวข้อต่างๆ การทำความเข้าใจแต่ละหัวข้อเหล่านั้นอย่างถ่องแท้และการค้นหาว่าพวกเขาไม่ได้ผลจะใช้เวลานานในฐานะผู้ที่ไม่ใช่นักเข้ารหัสลับ/นักคณิตศาสตร์ ดังนั้นฉันจึงรู้สึกขอบคุณสำหรับคำแนะนำเกี่ยวกับหัวข้อต่างๆ ที่อาจได้ผล
kodlu avatar
sa flag
ไม่ต้องกังวล ฉันยินดีช่วยเมื่อฉันทำได้ คุณหมายถึงอะไรโดย 3D?
J. Doe avatar
at flag
สิ่งที่จัดเรียงคล้ายกับ torus 3 มิติ ดังนั้นชุดของค่าที่เป็นวงกลมใน 3 ทิศทาง (+ ทิศทางผกผัน & ขนาดเท่ากันในแต่ละทิศทาง) ไม่จำเป็นต้องมี 6 ทิศทางสำหรับสมาชิกแต่ละคน (เช่นสำหรับ $x^{\alpha_i} \bmod N$ กับ 6 ที่เหมาะสม $\alpha_i$) บางเครือข่ายที่มีโหนดที่มีเพื่อนบ้าน $1$ ถึง $n$ ก็ใช้งานได้เช่นกัน อย่างไรก็ตาม พื้นที่ใกล้เคียงของสมาชิกหนึ่งคนจะต้องสามารถแสดงได้ในระนาบ 2D สามระนาบ (ถ้าจำไม่ผิดก็คือ 2-torus สามระนาบ) โดยมีจุดตัดของสมาชิกนั้น ความหนาแน่นของโหนดต้องเท่ากันทุกที่ ..
J. Doe avatar
at flag
..จำเป็นต้องมีวิธีกำหนดแผนที่เพื่อนบ้านกับระนาบ ต้องมีบางอย่างเช่นรัศมีเพื่อนบ้าน - โหนดไม่สามารถมีเพื่อนบ้านทั่วพื้นผิวได้พูดแบบกราฟิกถ้าจุดสุ่มบนแผ่นกระดาษเป็นตัวแทนของสมาชิกที่แตกต่างกัน สมาชิกที่อยู่ใกล้ที่สุดน่าจะเป็นเพื่อนบ้านของเขา (หรือเพื่อนบ้านของเพื่อนบ้าน) (เราพันรอบเส้นขอบของแผ่น - ดังนั้นตาข่ายจึงเป็นวงจรในสองมิติเช่นใน 2- พรู). เพื่ออธิบายสิ่งที่ฉันกำลังมองหา เราให้จุด/โหนดทั้งหมดบนแผ่นงานนั้นเป็นตัวเลขด้วย ตัวเลขแต่ละตัวในแผ่นนั้นจึงมีชุดตัวเลขเป็นเพื่อนบ้านแบบสองทิศทาง..
J. Doe avatar
at flag
..นอกจากนั้น ตัวเลขยังสามารถมีเพื่อนบ้าน (อื่นๆ) ได้อีกถึง 2 แผ่น (แผ่นละ 2 แผ่น) หากตัวเลขหลายตัวอยู่บนกระดาษสองแผ่นที่แตกต่างกัน (2-tori) ตัวเลขทั้งหมดจะวางอยู่บนบรรทัดเดียว (1-torus) - เหมือนที่จุดตัดของ 2-tori สองแผ่น ด้วยวิธีนี้ ระยะห่างของโหนด/ขอบข้างเคียงจะเท่ากันระหว่างโหนดเหล่านั้น อย่างน้อย $2^{32}$ โหนดอยู่ที่ 3 แผ่นงาน เมื่อพิจารณาจากสมาชิกแบบสุ่ม 2 คน การค้นหาการเชื่อมต่อที่มีอยู่จากโหนดหนึ่งไปยังอีกโหนดหนึ่งควรยากที่สุดเท่าที่จะเป็นไปได้ (เกี่ยวข้องกับจำนวนสมาชิกทั้งหมด) (เป้าหมายประมาณ $2^{100}$ ขั้นตอนการคำนวณ)...
J. Doe avatar
at flag
..ฝ่ายตรงข้ามยังสามารถเรียกใช้โปรแกรมและสร้างค่า/โหนดแบบสุ่ม ไม่ค่อยดีนัก แต่สามารถมีโครงสร้างเดียวกันได้หลายอินสแตนซ์ (ไม่เกิน 10) - ดังนั้นสำหรับโหนดสุ่มมีโอกาส (ประมาณค่าคงที่) เท่านั้นที่จะเชื่อมต่อ จะดีที่สุดหากสามารถสร้างโหนดแบบสุ่มของอินสแตนซ์เป้าหมายเดียวโดยไม่ทำให้ข้อมูลที่เกี่ยวข้องกับความปลอดภัยรั่วไหล ขนาดสมาชิกทั้งหมด (รวมถึงอินสแตนซ์) ควรมีขนาดเล็กที่สุดเท่าที่จะเป็นไปได้ (กรณีที่ดีที่สุดคือ $\around 2^{100}$ สมาชิก (อาจทำงานได้เฉพาะกับโหนด), $\about 2^{150}$ สมาชิก หากปัญหาคือ ไม่ลดเหลืออย่างละ 1D )...
J. Doe avatar
at flag
..นี่ฉันคิดว่าเป็นคำอธิบายปัญหาทั่วไปที่สุด ถ้าเรากลับไปจัดแนว $6$-neighborhood มันจะเป็น $x^{\alpha_i} \bmod N$ กับ 6 $\alpha_i$ ที่เหมาะสมอีกครั้ง สำหรับขนาดสมาชิกที่สูงกว่า เช่น สมาชิก $2^{218}$ สมาชิก EC อาจเป็นโซลูชันย่อยที่เหมาะสมที่สุด (ไม่ใช่ 3-torus)ด้วย $2^{300}$ สมาชิก $x^\alpha$ ทำหน้าที่ - แต่นั่นเป็นวิธีที่สมาชิกหลายคน...
J. Doe avatar
at flag
.. พวกเขาจะทำหน้าที่เป็นแบบยุคลิดและการจัดเรียงเมล็ดแบบสุ่ม แต่สอดคล้องกันสำหรับ RNG ซึ่งสามารถสร้างซ้ำได้เริ่มต้นที่จุดสุ่มและดำเนินการแบบยุคลิดใกล้กับเพื่อนบ้านและในที่สุดก็ส่งผลให้ (หลังจากเวลาไม่มีที่สิ้นสุดสำหรับรุ่น) สอดคล้องกัน ( ความลับ) โครงสร้าง ....และนานเกินไปอีกครั้ง ขอบคุณที่อ่านถ้าคุณมาถึงจุดนั้น

โพสต์คำตอบ

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