ค้นหาองค์ประกอบของ $\mathbb{Z}_p$ หากทราบลำดับขององค์ประกอบนั้น

mangart

5/5/23 21:48

ฉันมีเลขเฉพาะสองตัว $p$ (1024 บิต) และ $คิว$ (160 บิต) เช่นนั้น $คิว$ แบ่ง $p-1$. ตอนนี้ฉันต้องการหาองค์ประกอบ $ข$ ใน $\mathbb{Z}_p$ ด้วยคำสั่งของ $คิว$. นั่นหมายความว่า $b^q \equiv 1 \mod p$.

ฉันพยายามเลือก $ข$ โดยการสุ่มและตรวจสอบว่ามีความสอดคล้องกันหรือไม่ แต่ดูเหมือนว่านี่ไม่ใช่แนวทางที่ดีเนื่องจากไม่ได้ให้คำตอบในเวลาที่เหมาะสม มีวิธีใดที่จะค้นพบ $ข$ อย่างมีประสิทธิภาพ?

0 + 0

ทฤษฎีกลุ่ม

จำนวนเฉพาะ

เลขคณิตโมดูลาร์

Mikero

5/5/23 22:00

ฉันคิดว่านี่เป็นคำถามที่แตกต่างออกไป เพราะการค้นหาตัวสร้างโดยการลองผิดลองถูกจะง่ายกว่าการหาองค์ประกอบที่มีลำดับต่างกัน ฉันคิดว่าความน่าจะเป็นที่จะชนกับองค์ประกอบที่มีลำดับไม่สำคัญคือ $1 - \varphi(n)/n$ ซึ่งโดยทั่วไปแล้วใกล้เคียงกับศูนย์เล็กน้อย (ความน่าจะเป็นของการชนกับตัวสร้างคือ $\varphi(n)/n$) สิ่งนี้ชี้ให้เห็นถึงความต้องการวิธีการที่มีประสิทธิภาพมากกว่าการลองผิดลองถูกซึ่งใช้ได้ผลในการค้นหาเครื่องกำเนิดไฟฟ้า

ตอบกลับ

kelalaka

5/5/23 22:01

**จากคำตอบของ Poncho:** วิธีง่ายๆ อย่างหนึ่งในการเลือกตัวสร้างแบบสุ่มคือการเลือกค่าสุ่ม $h$ ระหว่าง 2 ถึง $p-1$ และคำนวณ $h^{(p-1)/q} \bmod p$; ถ้าค่านั้นไม่ใช่ 1 (และมีความเป็นไปได้สูง มันจะไม่เป็น) ดังนั้น $h^{(p-1)/q} \bmod p$ คือตัวสร้างแบบสุ่มของคุณ

ตอบกลับ

mangart

5/5/23 22:15

@kelalaka เท่าที่ฉันรู้ว่าตัวสร้างเป็นองค์ประกอบที่สามารถสร้างองค์ประกอบทั้งหมดของกลุ่มได้ ดังนั้นลำดับขององค์ประกอบนั้นจะเป็น $p-1$ แต่ฉันกำลังพยายามหาองค์ประกอบ $b$ ที่มี คำสั่ง $q$ ซึ่งเล็กกว่า $p-1$ และ $b$ ตามคำจำกัดความนี้ไม่ได้เป็นตัวสร้างของกลุ่ม

ตอบกลับ

kelalaka

5/5/23 22:19

นั่นคือสิ่งที่คำตอบรวมถึง อ่านอย่างละเอียด.

ตอบกลับ

mangart

5/5/23 22:39

@kelalaka โอ้ฉันเข้าใจแล้วคำตอบนั้นอยู่ในบทความ Wikipedia ที่เชื่อมโยงในคำตอบนั้นเกี่ยวกับกลุ่ม Schnorr นั่นตอบคำถามของฉันจริงๆ ขอบคุณมากและขออภัยที่ไม่ได้อ่านคำถามที่คุณแนะนำอย่างละเอียดในครั้งแรก

ตอบกลับ

poncho

5/5/23 22:56

ถ้า $q$ เป็นจำนวนเฉพาะ คำตอบของฉันคือคำตอบที่ถูกต้อง ถ้าไม่ใช่ แต่ทราบการแยกตัวประกอบแล้ว คำตอบของฉัน (ซึ่งการทดสอบหลังแบบง่ายๆ บางอย่างใช้ได้ผล) หากไม่ทราบการแยกตัวประกอบ ฉันก็ไม่เชื่อว่ามีวิธีที่ได้ผลตลอดเวลา (แต่คุณสามารถหาวิธีที่ใช้ได้กับความน่าจะเป็น $> 0.99$

ตอบกลับ

Kulap

คำถามนี้เป็นภาษาอื่นๆ:

EN: Finding an element of $\mathbb{Z}_p$ if the order of that element is known

TH: ค้นหาองค์ประกอบของ $\mathbb{Z}_p$ หากทราบลำดับขององค์ประกอบนั้น

RO: Găsirea unui element de $\mathbb{Z}_p$ dacă ordinea acelui element este cunoscută

RU: Нахождение элемента $\mathbb{Z}_p$, если известен порядок этого элемента

VI: Tìm một phần tử của $\mathbb{Z}_p$ nếu biết thứ tự của phần tử đó

โพสต์คำตอบ

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