ผกผันคูณใน ${GF}(2^4)$
ฉันต้องการสร้างไฟล์ $4\times4$ ตารางผกผันคูณใน $GF(2^4)$. พหุนามดั้งเดิมที่กำหนดคือ$P(x)= x^4+x+1$
(หมายเหตุ: ค่าในตารางต้องอยู่ในรูปแบบเลขฐานสิบหกดังนั้นฉันจะใช้ทั้งรูปแบบพหุนามและเลขฐานสิบหกในคำถามต่อจากนี้ไป)
ตอนนี้ฉันสามารถคำนวณผกผันการคูณสำหรับแถวแรกของเมทริกซ์คือ (00,01,02,03) ผกผันของ03หรือ$(x+1)$ออกมาเป็น0Eหรือ$(x^3+x^2+x)$.
อย่างไรก็ตามเมื่อฉันพยายามคำนวณผกผันของ10หรือ$x^4$มันออกมาอีกครั้ง0Eหรือ$(x^3+x^2+x)$. เป็นไปได้ไหมที่พหุนามสองตัวมีผกผันเหมือนกันทุกประการ? ถ้าไม่ฉันคิดไม่ออกว่าฉันจะทำอะไรผิด กรุณาช่วย.
คำตอบ
ทุ่งกาลัวส์ $\operatorname{GF}(2^4)$ (แสดงด้วย $\mathbb{F_{2^4}}$) ประกอบด้วย $16 = 2 ^4$องค์ประกอบ คำจำกัดความที่เป็นทางการคือ;
$\mathbb{F_{2^4}}$ คือแหวนผลหาร $\mathbb{F_{2}}[X]/(x^4 = x + 1)$ ของแหวนพหุนาม $\mathbb{F_{2}}[X]$ โดยอุดมคติที่สร้างขึ้นโดย $(x^4 = x + 1)$ เป็นเขตข้อมูลของคำสั่ง $2^4$.
เราสามารถแสดงรายการองค์ประกอบของ $\operatorname{GF}(2^4)$ เกี่ยวกับการแสดงพหุนามด้วยการกำหนดพหุนามดั้งเดิมกล่าวคือ $$a_3 x^3+a_2 x^2+a_1 x+a_0$$ ที่ไหน $a_i \in \operatorname{GF}(2)$ สำหรับ $i=0,1,2,3$.
$\operatorname{GF}(2^4)$ เป็นฟิลด์ดังนั้นทุกองค์ประกอบจึงมีผกผันการคูณที่ไม่ซ้ำกันยกเว้นศูนย์
$x^4$อย่างที่เราเห็นไม่ใช่องค์ประกอบของสนาม แต่เราสามารถลดได้ด้วยความช่วยเหลือของสมการของพหุนามที่กำหนด $x^4 = x + 1$. ดังนั้นจึงมีการแสดงเช่นเดียวกันกับ$x+1$ ในสนามดังนั้นผกผันจึงเหมือนกัน
นอกจากนี้ตารางผกผันการคูณยังมี $2\times 16$ ขนาดจึงมีเพียงแถวเดียว (หรือคอลัมน์) ในการคำนวณ
\ start {array} {| c | c |} \ hline p (x) \ ใน GF (2 ^ 4) & ผกผัน \\ \ hline 1 & 1 \\\ hline x & x ^ 3 + 1 \\\ hline x + 1 & x ^ 3 + x ^ 2 + x \\\ hline x ^ 2 & x ^ 3 + x ^ 2 + 1 \\\ hline x ^ 2 + 1 & x ^ 3 + x + 1 \\\ hline x ^ 2 + x & x ^ 2 + x + 1 \\\ hline x ^ 2 + x + 1 & x ^ 2 + x \\\ hline x ^ 3 & x ^ 3 + x ^ 2 + x + 1 \\\ hline x ^ 3 + 1 & x \\\ hline x ^ 3 + x & x ^ 3 + x ^ 2 \\\ hline x ^ 3 + x + 1 & x ^ 2 + 1 \\\ hline x ^ 3 + x ^ 2 & x ^ 3 + x \\\ hline x ^ 3 + x ^ 2 + 1 & x ^ 2 \\\ hline x ^ 3 + x ^ 2 + x & x + 1 \\\ hline x ^ 3 + x ^ 2 + x + 1 & x ^ 3 \\\ hline \ end {array}
องค์ประกอบที่ไม่ใช่ศูนย์ของฟิลด์มักแสดงโดยการเพิ่มดาวที่ด้านขวาบน $\mathbb{F}^*_{2^4} = \mathbb{F}_{2^4}- \{0\}$ สร้างกลุ่มวัฏจักรทวีคูณ $\mathbb{F}^*_{2^4}$ สามารถสร้างได้โดย $x$เช่น $\mathbb{F}^*_{2^4} = \langle x \rangle$. พลังของเครื่องกำเนิดไฟฟ้า
\ start {array} {| c | c |} \ hline i & x ^ i \\ \ hline x ^ 1 & x \\ \ hline x ^ {2} & x ^ 2 \\ \ hline x ^ {3} & x ^ 3 \\ \ hline x ^ {4} & x + 1 \\ \ hline x ^ {5} & x ^ 2 + x \\ \ hline x ^ {6} & x ^ 3 + x ^ 2 \ \ \ hline x ^ {7} & x ^ 3 + x + 1 \\ \ hline x ^ {8} & x ^ 2 + 1 \\ \ hline x ^ {9} & x ^ 3 + x \\ \ hline x ^ {10} & x ^ 2 + x + 1 \\ \ hline x ^ {11} & x ^ 3 + x ^ 2 + x \\ \ hline x ^ {12} & x ^ 3 + x ^ 2 + x + 1 \\ \ hline x ^ {13} & x ^ 3 + x ^ 2 + 1 \\ \ hline x ^ {14} & x ^ 3 + 1 \\ \ hline x ^ {15} & 1 \\ \ hline x ^ {16} & x \\ \ hline \ end {array} $p(x) = 0$ ไม่รวมเนื่องจากไม่มีผกผันแบบทวีคูณ
ด้านล่างนี้คือรหัส SageMath ที่ใช้ในคำตอบนี้
#Base field
R.<y> = PolynomialRing(GF(2), 'y')
#Defining polynomial
G = y^4+y+1
#The field extension
S.<x> = QuotientRing(R, R.ideal(G))
S.is_field()
for p in S:
if ( p != 0 ):
print( p, " - ", 1/p )