Program pentru a afla inversul polinomului

Poate cineva să-mi spună cum să găsesc inversul unui polinom dat folosind programarea python? De exemplu: intrarea dată este de a găsi inversul lui (x^2 + 1) modulo (x^4 + x + 1). ieșirea ar trebui să fie: (x^3 + x + 1).

Pentru a calcula inversarea lui $P$ modulo $Q$ cu $Q$ de grad $n+1$, o soluție ușoară ar putea fi rezolvarea unui sistem liniar cu necunoscută: $\lambda_0, \dots, \lambda_n$ astfel încât $P^{-1}= \sum \lambda_i X^i$.

Atunci știm $(P \cdot(\sum \lambda_i X^i) )\mod Q = 1$. Și căutând egalitatea pentru fiecare coordonată, avem $n+1$ ecuatii cu $n+1$ necunoscute. Și ecuațiile sunt independente dacă și numai dacă $P$ este inversabilă în $\mathbb{Z}_p[X]/(Q\mathbb{Z}_p[X])$.

Cu exemplul tău $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}

Dacă rezolvi sistemul liniar, vei găsi soluția $\lambda_2=0$ și $\lambda_1=\lambda_3=\lambda_0=1$.

Ei bine, Sagemath poate rezolva acest lucru și, după cum știm, SageMath folosește Python. Este posibil și inversul! Instalați pachetul prin;

pip3 instalează sagemath

Acum suntem gata să folosim codul SageMath

k = GF(2)
R.<x> = k[]
k.extensie(x^4 + x + 1, „a”)
imprimare (k)

p = (x^2 + 1)

print(p)

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

print(q)

Însă R.<x> = k[] nu este analizabil de către python. Trebuie să folosim pregăti pentru a forma codul python.

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

Deci codul python este

din import sage.all *

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

imprimare (K)

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

Aceasta iese;

Câmp finit într-o dimensiune de 2^4
x^2 + 1
x^3 + x + 1

Mulțumiri lui John Palmieri pe pregăti