1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Nov 2, 2016 at 20:02
  • $\begingroup$ @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. $\endgroup$
    – Eric
    Nov 3, 2016 at 11:22
  • $\begingroup$ 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. $\endgroup$ Nov 3, 2016 at 16:49
  • $\begingroup$ @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. $\endgroup$
    – Eric
    Nov 4, 2016 at 16:17

1 Answer 1

2
$\begingroup$

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[106]= {{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[111]= 1 + x + x^2 + x^2 y *)
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Szabolcs
    Nov 9, 2016 at 10:43
  • $\begingroup$ @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. $\endgroup$ Nov 9, 2016 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.