求多項式逆的程序

誰能告訴我如何使用 python 程式找到給定多項式的逆？例如：給定的輸入是求 (x^2 + 1) 模 (x^4 + x + 1) 的倒數。輸出應該是：(x^3 + x + 1)。

計算的倒數 $ P $ 模組 $ Q $ 和 $ Q $ 學位 $ n+1 $ ，一個簡單的解決方案可能是求解一個未知的線性系統： $ \lambda_0, \dots, \lambda_n $ 這樣 $ P^{-1}= \sum \lambda_i X^i $ .

然後我們知道 $ (P \cdot(\sum \lambda_i X^i) )\mod Q = 1 $ . 通過尋找每個座標的相等性，我們有 $ n+1 $ 方程與 $ n+1 $ 未知數。並且方程是獨立的當且僅當 $ P $ 是可逆的 $ \mathbb{Z}_p[X]/(Q\mathbb{Z}_p[X]) $ .

以你的例子 $ n=3 $ . $$ \begin{align}((X^2 +1) \cdot( \lambda_0 + \lambda_1 X + \lambda_2 X^2 + \lambda_3 X^3) )\mod (X^4 + X + 1) = 1 \ \lambda_0 + \lambda_1 X + (\lambda_2+\lambda_0) X^2 + (\lambda_3+ \lambda_1) X^3 + (\lambda_2 + \lambda_3X) X^4= 1 \ \lambda_0 + \lambda_1 X + (\lambda_2+\lambda_0) X^2 + (\lambda_3+ \lambda_1) X^3 + (\lambda_2 + \lambda_3X) (-X-1)= 1 \ (\lambda_0-\lambda_2) + (\lambda_1- \lambda_2 - \lambda_3) X + (\lambda_2+\lambda_0-\lambda_3) X^2 + (\lambda_3+ \lambda_1) X^3 = 1 \end{align} $$

如果你解決線性系統，你會找到解決方案 $ \lambda_2=0 $ 和 $ \lambda_1=\lambda_3=\lambda_0=1 $ .

好吧，SageMath 可以解決這個問題，而且我們知道 SageMath 使用 Python。反過來也是可以的！通過以下方式安裝軟體包；

pip3 install sagemath

現在我們準備好使用 SageMath 程式碼了

k = GF(2)
R.<x> = k[]
k.extension(x^4 + x + 1, 'a')
print(k)

p = (x^2 + 1)

print(p)

q = p.inverse_mod(x^4 + x + 1)

print(q)

但是，R.<x> = k[]python 無法解析。我們必須使用preparse來形成 python 程式碼。

preparse('R.<x> = k[]')
"R = k['x']; (x,) = R._first_ngens(1)"

所以python程式碼是

from sage.all import *

F = GF(2)
R = F['x']; (x,) = R._first_ngens(1)
K = F.extension(x**4 + x + 1, 'a')

print(K)

p = (x**2 + 1)
print(p)
q = p.inverse_mod(x**4 + x + 1)
print(q)

這輸出；

Finite Field in a of size 2^4
x^2 + 1
x^3 + x + 1

---

感謝 John Palmieri 的預解析

引用自：https://crypto.stackexchange.com/questions/96049