Score:2

Program to find the inverse of polynomial

mx flag

Can anyone tell me how to find the inverse of a given polynomial using python programming? Ex: input given is to find the inverse of (x^2 + 1) modulo (x^4 + x + 1). the output should be : (x^3 + x + 1).

Daniel S avatar
ru flag
This [finite field package](https://pypi.org/project/pyfinite/) seems to have the Ffield.Inverse() method.
Score:1
cn flag

To compute the invert of $P$ modulo $Q$ with $Q$ of degree $n+1$, an easy solution could be to solve a linear system with unknown: $\lambda_0, \dots, \lambda_n$ such that $P^{-1}= \sum \lambda_i X^i$.

Then we know $(P \cdot(\sum \lambda_i X^i) )\mod Q = 1$. And by looking the equality for every coordinate, we have $n+1$ equations with $n+1$ unknowns. And the equations are independent if and only if $P$ is invertible in $\mathbb{Z}_p[X]/(Q\mathbb{Z}_p[X])$.

With your example $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}

If you solve the linear system, you will find the solution $\lambda_2=0$ and $\lambda_1=\lambda_3=\lambda_0=1$.

Score:1
in flag

Well, Sagemath can solve this, and as we know the SageMath uses Python. The reverse is also possible! Install the package by;

pip3 install sagemath

Now we are ready to use the SageMath code

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)

However, the R.<x> = k[] is not parsable by python. We have to use preparse to form python code.

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

So the python code is

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)

This outputs;

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

Thanks to John Palmieri on the preparse

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.