Score:0

ค้นหาการผกผันการคูณในฟิลด์ Galois $2^8$ โดยใช้อัลกอริทึมแบบยุคลิดแบบขยาย

ธง sx

ฉันกำลังจัดการกับทุ่ง Galois $GF(2^{8})$ และต้องการความช่วยเหลือในการค้นหาก พหุนาม $r^{-1}(x)$ ดังนั้น $r^{-1}(x) r(x) \equiv 1 \mod m(x)$, ที่ไหน:

  • $m(x) = x^{8} + x^{4} + x^{3} + x + 1$
  • $r(x) = u(x) - q(x) \cdot ม.(x)$
  • $u(x) = s(x) \cdot t(x)$
  • $s(x) = x^{7} + x^{5} + x^{4} + x$
  • $t(x) = x^{4} + x^{2} + 1$

ดังนั้น:

  • $u(x) = x^{11} + x^{8} + x^{6} + x^{4} + x^{3} + x$
  • $q(x) = x^{3} + 1$
  • $r(x) = -x^{7} - x^{4} - x^{3} + 1 \mod 2 = x^{7} + x^{4} + x^{3} + 1$

สิ่งที่ฉันได้ลอง

ฉันได้พยายามที่จะค้นหา $r^{-1}(x)$ แต่ล้มเหลว

นี่คือสิ่งที่ฉันได้ลอง:

จากอัลกอริทึมของ Euclides:

\begin{align*} คุณ(x) &= q(x) \cdot ม(x) + r(x) \ m(x) &= q_{2}(x) \cdot r(x) + r_{2}(x) \ &= x \cdot r(x) + (-x^{5} + x^{3} + 1 \mod 2) \ &= x \cdot r(x) + ( x^{5} + x^{3} + 1) \ r(x) &= q_{3}(x) \cdot r_{2}(x) + r_{3}(x) \ &= (x^{2} - 1 \mod 2) \cdot r_{2}(x) + (x^{4} + 2 x^{3} - x^{2} + 2 \mod 2) \ \ &= (x^{2} + 1) \cdot r_{2}(x) + (x^{4} + x^{2}) \ r_{2}(x) &= q_{4}(x) \cdot r_{3}(x) + r_{4}(x) \ &= x \cdot r_{3}(x) + 1 \ r_{3}(x) &= q_{5}(x) \cdot r_{4}(x) + r_{5}(x) \ &= (x^{4} + x^{2}) \cdot r_{4}(x) + 0 \end{จัดตำแหน่ง*}

เรามี:

\begin{align*} q_{2}(x) &= x \ q_{3}(x) &= x^{2} + 1 \ q_{4}(x) &= x \ q_{5}(x) &= x^{4} + x^{2} \ r_{2}(x) &= x^{5} + x^{3} + 1 \ r_{3}(x) &= x^{4} + x^{2} \ r_{4}(x) &= 1 \ r_{5}(x) &= 0 \end{จัดตำแหน่ง*}

ดังนั้น:

\begin{align*} 1 &= r_{4}(x) \ &= r_{2}(x) - q_{4}(x)r_{3}(x) \ &= r_{2}(x) - q_{4}(x)\big(r(x) - q_{3}(x)r_{2}(x)\big) \ &= \big(-q_{4}(x)\big) r(x) + \big(1 + q_{3}(x)\big) r_{2}(x) \ &= \big(-q_{4}(x)\big) r(x) + \big(1 + q_{3}(x)\big) \big(m(x) - q_{2}(x)r(x)\big) \ &= \ใหญ่(-q_{4}(x) - q_{2}(x) - q_{2}(x)q_{3}(x)\ใหญ่) r(x) + \ใหญ่(1 + q_{r}(x)\ใหญ่) ม.(x) \end{จัดตำแหน่ง*}

ดังนั้นเราจึงได้รับ:

\begin{align*} r^{-1}(x) & = - q_{4}(x) - q_{2}(x) - q_{2}(x)q_{3}(x) & \mod 2 \ & = - x - x - x(x^{2} + 1) & \mod 2 \ & = - x - x - x^{3} - x & \mod 2 \ & = - x^{3} - 3x & \mod 2 \ & = x^{3} + x \end{จัดตำแหน่ง*}

แต่นี่ผิดเพราะเมื่อฉันคำนวณ $r^{-1}(x) r(x) \mod m(x)$ ผลลัพธ์ไม่ใช่ 1

us flag
"mod 2" มาจากไหน
blackyellow avatar
sx flag
@SamGinrich mod 2 เป็นเพราะเราอยู่ใน $GF(2^n)$
us flag
$GF(2^n)$ เป็นโมดูโลบางอย่าง $m(x)$
blackyellow avatar
sx flag
ขอโทษ ฉันไม่เข้าใจ ฉันทำอะไรผิด..ฉันมีปัญหาในการทำความเข้าใจอัลกอริทึม (นั่นคือเหตุผลที่ฉันต้องการความช่วยเหลือ) ฉันคำนวณ $\mod 2$ เพราะฉันคิดว่าค่าสัมประสิทธิ์พหุนามต้องอยู่ใน $\{0,1\}$ เนื่องจากเรากำลังจัดการกับไบต์ หากคุณสามารถอธิบายสิ่งที่ฉันทำผิดได้ ฉันจะขอบคุณมาก!
fgrieu avatar
ng flag
ฉันเดาว่ามันต้องการโพลิโนเมียลผกผันของ $s(x)\cdot t(x)$ modulo $m(x)$ และสำหรับสิ่งนี้ คุณกำหนด $r(x)=s(x)\cdot t(x)\ bmod ม.(x)$. หากไม่มีคำจำกัดความนี้ ฉันไม่เข้าใจ _thus_ $u(x)=s(x)\cdot t(x)$
blackyellow avatar
sx flag
@fgrieu ฉันลืมพูดถึงว่า $u(x) = s(x) \cdot t(x)$ เพราะมันถูกกำหนดด้วยวิธีนี้ในปัญหา
Score:1
ธง ng

ปัญหาคือที่ไหน $$r_{2}(x) - q_{4}(x)\big(r(x) - q_{3}(x)r_{2}(x)\big)$$กลายเป็น$$\big(-q_{4}(x)\big) r(x) +\big(1 + q_{3}(x)\big) r_{2}(x)$$เมื่อนั้นควรจะเป็น$$\big(-q_{4}(x)\big) r(x) +\big(1 + q_{4}(x)\cdot q_{3}(x)\big) r_{2}( x)$$


ฉันคิดว่าจะเป็นการดีที่สุดถ้าใช้อัลกอริทึมที่ง่ายกว่ามาก ที่นั่นซึ่งต้องติดตามเพียง 4 ตัวแปรเท่านั้น

blackyellow avatar
sx flag
ขอขอบคุณ! นั่นคือสิ่งที่ฉันคิดผิด! พระเจ้าอวยพรคุณเพราะฉันมีความเครียดมากกับคำถามนี้ ...
blackyellow avatar
sx flag
อย่างไรก็ตาม ฉันใช้อัลกอริทึมที่ง่ายกว่าที่คุณพูดถึงแทนที่จะใช้ก่อนหน้านี้.... ขอบคุณ!

โพสต์คำตอบ

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