Программа для нахождения обратного многочлена

Может ли кто-нибудь сказать мне, как найти инверсию заданного полинома с помощью программирования на Python? Пример: данный ввод состоит в том, чтобы найти инверсию (x ^ 2 + 1) по модулю (x ^ 4 + x + 1). вывод должен быть: (x^3 + x + 1).

Чтобы вычислить инвертирование $P$ по модулю $Q$ с $Q$ степени $n+1$, простым решением может быть решение линейной системы с неизвестным: $\лямбда_0,\точки,\лямбда_n$ такой, что $P^{-1}= \сумма \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{выравнивание}

Если вы решите линейную систему, вы найдете решение $\лямбда_2=0$ и $\лямбда_1=\лямбда_3=\лямбда_0=1$.

Ну, Sagemath может решить эту проблему, и, как мы знаем, SageMath использует Python. Обратное тоже возможно! Установите пакет;

pip3 установить sagemath

Теперь мы готовы использовать код SageMath.

к = GF(2)
Р.<х> = к[]
k.расширение (х ^ 4 + х + 1, 'а')
печать (к)

р = (х^2 + 1)

печать (р)

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

распечатать (к)

Однако Р.<х> = к[] не анализируется python. мы должны использовать готовить для формирования кода Python.

подготовить('R.<x> = k[]')
"R = k['x']; (x,) = R._first_ngens(1)"

Итак, код Python

из sage.all импорт *

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

печать(К)

р = (х**2 + 1)
печать (р)
q = p.inverse_mod (x ** 4 + x + 1)
распечатать (к)

Это выходы;

Конечное поле размером 2^4
х^2 + 1
х^3 + х + 1

Спасибо Джону Палмиери за готовить