Finding inverse polynomial in $\mathbb{F}_p[x]/(\psi)$ with maple

Question

I need help with maple. I want to invert the polynomials $(x^{361}-x)^2$ and $4(x^3+2x+1)^{19}$ with the help of maple. The problem is that we are working in $\mathbb{F}_{19}[X]$ and modulo $\psi(x)=5x^{12}+10x^{10}+17x^8+5x^7+x^6+9x^5+12x^4+2x^3+5x^2+8x+8$. I know, the polynomials are really ugly. But I need them for Schoof's algorithm to count points on elliptic curves...

Thanks in advance for every hint! (I am a bloody maple beginner...) Magda

Answer 1

f := (x^361 - x)^2;
g := 4*(x^3 + 2*x + 1)^19;
p := 5*x^12 + 10*x^10 + 17*x^8 + 5*x^7 + x^6 + 9*x^5 + 12*x^4 + 2*x^3 + 5*x^2 + 8*x + 8;

# reduce wrt field relation
f := Rem(f,p,x) mod 19;  
g := Rem(g,p,x) mod 19;

# compute f1 = inverse of f
Gcdex(f,p,x,'f1') mod 19;
# verify f*f1 = 1
Rem(f*f1,p,x) mod 19;

# compute g1 = inverse of g
Gcdex(g,p,x,'g1') mod 19;
# verify g*g1 = 1
Rem(g*g1,p,x) mod 19;