如何使用擴展歐幾里得算法來反轉有限域元素？
我正在做一些密碼學練習（我是這個主題的新手）並且想知道以下問題甚至意味著什麼或者它要求我找到什麼。我確實知道如何做擴展歐幾里得算法，但我不知道如何將它應用於這個問題。我不需要它的答案，但我希望有人向我解釋這個問題的要求。
使用擴展歐幾里得算法手動計算： $ (\mathtt{0x35})^{-1} $ 在 $ \operatorname{GF}(2^8) $ 與不可約多項式 $ m(x) = (\mathtt{0x11B}) $ . (2 分)
（注意：這是 AES 使用的有限域，’ $ \mathtt{0x} $ ’ 表示十六進製表示。）
要回答這個問題，我們需要了解以下內容的含義：
領域_ $ \operatorname{GF}(2^8) $ 由不可約多項式生成 $ m(x) = (\mathtt{0x11B}) $ .
我將嘗試對它進行溫和、漸進的介紹。
查看該欄位的一種簡單方法是，作為 256 個八位字節的集合 $ {\mathtt{0x00},\mathtt{0x01},\dots,\mathtt{0xFF}} $ ; 加法按位異或 $ \oplus; $ ; 和乘法交換運算 $ * $ 以下列任一方式定義：
- 有了 $ \mathtt{0x01} $ 作為中性元素， $ \mathtt{0x02}\mathtt{0x80}=\mathtt{0x1B}; $ （這是給定的 $ \mathtt{0x11B} $ 截斷為低 8 位），並且更直覺 $ \mathtt{0x02}\mathtt{0x02}=\mathtt{0x04}; $ , $ \mathtt{0x02}\mathtt{0x04}=\mathtt{0x08}; $ , $ \mathtt{0x02}\mathtt{0x08}=\mathtt{0x10}; $ , $ \mathtt{0x02}\mathtt{0x10}=\mathtt{0x20}; $ , $ \mathtt{0x02}\mathtt{0x20}=\mathtt{0x40}; $ , $ \mathtt{0x02}*\mathtt{0x40}=\mathtt{0x80}; $ . 這些和屬性 $ * $ (交換 性,結合性,相對於 $ \oplus; $ ) 足以完全定義 $ * $ . 常數 $ \mathtt{0x1B} $ 是這樣的，除了 $ \mathtt{0x00} $ （中性元素 $ \oplus; $ ) 有一個乘法逆元，可以通過檢查乘法表來找到（建立這個表，並推導出一個算法來計算沒有這個表的兩個任意元素的乘積，最多 8 次迭代，作為推薦練習留給讀者）。這給出了問題中提出的結果，但不是通過方法思想，並且手工不切實際。
- 或者，我們可以定義一個交換環 $ (\mathbb N,\oplus,\otimes) $ 在哪裡 $ \oplus $ 是按位異或，並且 $ \otimes $ （有時稱為無進位乘法）當任一參數是 2 的冪且結合性為 $ \otimes $ 關於 $ \oplus $ 用於定義其他情況。例如 $ \mathtt{0xDB}\otimes\mathtt{0x42} $ $ =\mathtt{0xDB}\otimes(\mathtt{0x40}\oplus\mathtt{0x02}) $ $ =(\mathtt{0xDB}\otimes\mathtt{0x40})\oplus(\mathtt{0xDB}\otimes\mathtt{0x02}) $ $ =\mathtt{0x36C0}\oplus\mathtt{0x1B6} $ $ =\mathtt{0x3776} $ . 我們可以定義一個類似於歐幾里得除法 $ (\mathbb N,\oplus,\otimes) $ , 給出商 $ q $ 和休息 $ r $ 從股息 $ d $ 和非零除數 $ n $ , 這樣 $ d=(q\otimes n)\oplus r $ , 和位大小 $ r $ 小於位大小 $ n $ . 這允許我們在 $ (\mathbb N,\oplus,\otimes) $ 環中的模減少 $ (\mathbb Z,+,\times) $ . 我們的運營 $ * $ 在 $ \operatorname{GF}(2^8) $ 是 $ \otimes $ ，然後是減少模 $ m=\mathtt{0x11B} $ . 這個常數是這樣的 $ (\operatorname{GF}(2^8),\oplus,*) $ 是一個欄位，很像 $ (\mathbb Z_n,+,\times) $ 是一個欄位，當 $ n $ 是素數。現在我們可以應用擴展歐幾里得算法並通過所提出的方法回答問題。我們就像計算一個正整數的反模一樣，但是使用 $ \oplus $ 而不是加法和減法， $ \otimes $ 而不是乘法，以及歐幾里得除法的類比 $ (\mathbb N,\oplus,\otimes) $ .
查看欄位的等效方式 $ \operatorname{GF}(2^8) $ 是 256 個多項式的集合，其中一個變數的次數小於 8，每個布爾代數都有位係數；多項式相加法；乘法定律 多項式的乘法，然後是多項式乘積的模多項式歸約 $ m(x)=x^8+x^4+x^3+x+1 $ （對應於位 $ \mathtt{0x11B}; $ ）。除了零是可逆的之外，每個元素的充分必要條件是 $ m(x) $ 是不可約的，這成立。現在我們可以應用擴展歐幾里得算法並通過所提出的方法回答問題。我們就像計算一個正整數的反模一樣，但是使用 $ m(x) $ 作為模數，並用位係數對多項式進行除法，而不是歐幾里得除法。
對於使用擴展歐幾里得算法（許多可能性之一）時的反演本身，推薦的算法是這個。
TODO：添加上面的描述
擴展歐幾里得算法為兩個整數生成最大公約數和 Bézout 係數 $ a $ 和 $ b $ . 如果 $ gcd(a,b) = 1 $ 和 $ a<b $ ，那麼 Bézout 係數也給你乘法逆 $ a $ 在 $ \mathbb{Z}/b\mathbb{Z} $ .
因為擴展歐幾里得算法中使用的運算是在多項式上定義的，所以該過程可以應用於 $ GF(p^n) $ . 問題只是要求您應用算法並確定特定元素的乘法逆元。
顯然，分配這個問題的學生的學術成熟度水平並不要求他們熟悉十六進製表示法。