# How to perform an euclidian division in a Finite Field?

I am quite new to mathematica, I am looking for a function similar to QuotientRemainder[] but which works with finite fields as implemented by the FiniteFields package (update : or with any other package which handles finite fields). The input should be two elements of a finite field and the output should be the quotient and the remainder of the euclidian division of the two elements.

Thank you.

• Is there a compelling reason to use that package? It is not maintained and is known to not play nice with built in functions such as Together. Nov 2, 2016 at 20:02
• @DanielLichtblau absolutely none, I am just looking for a way to perform an euclidian division in a finite field, I just thought the FiniteFields package handled everything related to finite fields. I update my question.
– Eric
Nov 3, 2016 at 11:22
• There are a few possibilities. If your field is a prime field, simplest is to use PolynomialQuotientRemainder with a modulus set. If you are working over more general finite fields then it won't be quite so simple. I guess best would be to post an example or two showing what you have in mind. Nov 3, 2016 at 16:49
• @DanielLichtblau I am working with "general" finite fields like $(\mathbb{Z}/2\mathbb{Z})/(1+X^2+X^3)$, my elements would therefore be polynomials in the quotient field.
– Eric
Nov 4, 2016 at 16:17

Could use PolynomialReduce for this. We just add the extension-defining polynomial to the reducing one (the divisor). Here is an example.

extpoly = x^3 + x^2 + 1;
p1 = (x^2 + 1)*y^5 + (x + 1)*y^4 + (x^2 + x)*y^2 + y + (x^2 + x + 1);
p2 = y^4 + x^2*y^3 + (x^2 + 1)*y + 1;

{{q1, q2}, r} = PolynomialReduce[p1, {p2, extpoly}, {y, x}, Modulus -> 2]

(* Out= {{1 + x + x^2 + x^4 + y + x^2 y,
1 + x + y + x y + x^2 y + x^3 y + y^2 + x y^2 + x^2 y^3 + x^3 y^3},
1 + x + x^2 + x^2 y} *)


So the quotient is q1, modulo the polynomial that defines the extension. And the remainder is r.

Check this:

PolynomialMod[p1 - {q1, q2}.{p2, extpoly}, 2]

(* Out= 1 + x + x^2 + x^2 y *)

• Could you take a look at the first heading here? It's not the sort of 'bug' I would report. It' internal stuff and probably not even a bug. But maybe worth a glance for you? Nov 9, 2016 at 10:43
• @Szabolcs I do not have a strong opinion on this myself. I sent a link to some developers who might be more familuar with the function, in case they see cause to comment, add documentation or the like. Nov 9, 2016 at 15:30