# Question:How to work with polynomials over Finite Fields?

## Question:How to work with polynomials over Finite Fields?

Maple

TL;DR I'm having problems with the Finite Fields, polynomials over them and related operations. I saw it has been asked  but questions were asked long time ago. Any advice would be appreciated.

I'm trying to develop some algorithms in Maple using Finite Fields. I'm finding it difficult to learn Maple as I find the information on the internet either basic (guides on making sums and so) or too advanced (most of the times Maple Help feels like swimming in the abyss).

At first I started using the Domains package but it's documentation is quite ambiguous and I felt it was too low-level. I switched then to using the Galois Field package making statements like these:

```#Example of EUCLIDES algorithm in F7
p:=7:
G7:=GF(p,1);
a:=G7:-ConvertIn(6);
b:=G7:-ConvertIn(5);
gcd:=EUCLIDES(a, b, G7, p);```

At this moment, things get very confusing as a and b were elements of F7 but whattype returned they were zppolys. The problem arises when I try to use polynomials in F7[x]. Intuitively, I coded this:

```a := modp1(ConvertIn(3*x^6+2*x^2+x+5, x), 7);
b := modp1(ConvertIn(6*x^4+x^3+2*x+4, x), 7);
mcd:=EUCLIDES(a,b,G7, 7);```

as I found the modp1 functions diving in Maple Help. The strange thing is that a and b also claim to be zppolys. Is this normal? Do the elements and the polynomials over the elements have the same type? It's a bit odd.

Also, my implementation of EUCLIDES is as follows:

```proc(a::zppoly, b::zppoly, g::symbol, p::integer)
local r0, r1, r2;
r0, r1 := a, b;
while r1 <> g:-ConvertIn(0) do
r2 := modp1(Rem(r0,r1),p);
r0 := r1;
r1 := r2
end do;
return r0
end proc:```

Which syntax I find a bit annoying.

The problem gets even worse as I try to implement the Rabin test of irreducibility https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields#Rabin.27s_test_of_irreducibility

Which uses the modular composition algorithm, implemented as follows:

```modcomp := proc(f::zppoly, g::zppoly, h::zppoly, p::integer)
local n, m, A, B, i, pol, grad, k, j, BA, b, ri;
n := modp1(Degree(f));
m := ceil(n^(1/2));
A := Matrix(m,n);
B := Matrix(m,m);

for i from 1 to m do
pol := repsqua(h, i-1, f, p);

for k from 0 to grad do
A[i, k+1] := modp1(Coeff(pol, k));
end do;

for j from 1 to m do
B[i, j] := modp1(Coeff(g, (j-1)+(i-1)*m));
end do;
end do;

BA := B.A;
b := modp1(ConvertIn(0,x),p);

for i from 1 to m do
ri := modp1(ConvertIn(0,x),p);
pol := 0;
for j from 1 to m do
if j <= numelems(A[i]) then
pol := pol + A[i, j]*x^(j-1);
end if;
end do;
pol := modp1(ConvertIn(pol,x),p);
pol := repsqua(pol, i-1, f, p);
b := modp1(Add(b, modp1(Rem(modp1(Multiply(pol, ri)), f))));
end do;
return b;
end proc:```

That ceirtainly is an annoying syntax plus the fact that the whole implementation of the algorithm doesn't work. I upload a file in case someone has some time to have a look. testIrrFq.mw

I'm quite lost in all that goes about Polynomials and Finite Fields and so in Maple, so any help is appreciated.

﻿