Score:0

วิธีคำนวณค่าผกผันของฟังก์ชัน $x^3$ ใน $\mathbb{F}_{2^n}$

ธง mx

วิธีคำนวณส่วนผกผันของฟังก์ชัน $x^3$ ใน $\mathbb{F}_{2^n}$?, โมโนเมียลใดๆ $x^d$ เป็นการเปลี่ยนแปลงในสนาม $\mathbb{F}_{2^n}$ ถ้า $gdc(d,2^{n}-1)=1$,ทำไม?

kelalaka avatar
in flag
ยินดีต้อนรับสู่ [cryptography.se] $x^3$ ไม่ใช่ฟังก์ชัน แต่เป็นการแสดงพหุนามขององค์ประกอบของฟิลด์ $\mathbb F_{2^2}$ วิธีเริ่มต้นในการหาค่าผกผันคือการใช้ Extended-gcd กับพหุนาม หากคุณต้องการเพียงผลลัพธ์ ให้ใช้ SageMath คำถามนี้เป็นคำถาม HW หรือไม่
poncho avatar
my flag
@kelalaka: จริงๆ แล้ว ฉันเชื่อว่าโดย $x^3$ เขากำลังพูดถึงฟังก์ชัน $F(z) = z \cdot z \cdot z$ ซึ่งกำหนดไว้อย่างดีในทุกฟิลด์ เช่น $\mathbb{ Z}_{2^{n}}$
kelalaka avatar
in flag
@poncho การตีความของคุณดีกว่าของฉัน
Score:3
ธง ru

คำสั่งของกลุ่มการคูณของ $\mathbb F_{2^n}$ เป็น $2^n-1$. ถ้า 3 เป็นโคไพรม์ $2^n-1$ แล้วมีอยู่ $d\in [1,\ldots,2^n=1]$ ดังนั้น $3d\equiv 1\pmod{2^n-1}$. เราสามารถหาเช่น $d$ โดยใช้อัลกอริทึมแบบยุคลิดแบบขยาย

เปิดฟังก์ชั่น $\mathbb F_{2^n}$ $y\mapsto y^d$ จะเป็นการกลับกันของแผนที่ $x\mapsto x^3$ ตั้งแต่ $x\in\mathbb F_{2^n}^\times$ เรามี $(x^3)^d=x^{3d}=x^1$ (กรณี $x=0$ เห็นได้ชัด)

นี่หมายความว่า $x\mapsto x^3$ เป็น bijective และด้วยเหตุนี้การเปลี่ยนแปลง

ในกรณีที่ $3|2^n-1$, ถ้า $x^3=y$ ใน $\mathbb F_{2^n}$ แล้วจะทำอย่างไร $(\โอเมก้า x)^3=y$ และ $(\omega^2 x)^3=y$ ที่ไหน $\โอเมก้า$ คือรากที่สามของ 1 นิ้ว $\mathbb F_{2^n}$. ในกรณีนี้แผนที่ไม่ใช่การอัดฉีดและไม่ใช่การเรียงสับเปลี่ยน

โพสต์คำตอบ

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