5
$\begingroup$

Over $\mathbb{F}_{4}$, for example, I am looking for a function that will, for example, reduce the polynomial function (not an element of the finite field itself) $$x^5 + 6x^4 +x^3 + 1 \rightarrow x^2 + x^3 + 1$$

using the identity $x^q = x$ over a finite field of order $q$, and the fact that $p=0$ for the characteristic of the field $p$ (2 in the case above). Again, I am not looking for a way to reduce something modulo some irreducible polynomial. I am just looking for something that will reduce the powers (e.g., $x^5$ to $x^2$ in the example above) and convert any zero coefficients to zero (e.g., $6x^4$ in the example above)

I would also be interested in any potential ways to write such a function. I would need it to work over multiple variables (e.g., $x,y,z,...$) also. Maybe I could use an if statement to check if the power was greater than $q-1$, although with multiple summed terms and variables I wouldn't be completely sure how to do that.

Any advice would be appreciated... Thanks

EDIT: This function seems to work (modified from cvgmt's reply) as well as the one from Carl Woll's reply:

GFReduce[f_, p_, q_, var_] := PolynomialMod[PolynomialMod[f, p] //. var^k_ :> var^Mod[k, q - 1, 1], p];
$\endgroup$
1

3 Answers 3

3
$\begingroup$

I think you can use PolynomialReduce for this:

PolynomialReduce[
    x^5 + 6 x^4 + x^3 + 1,
    x^4 - x,
    x,
    Modulus->2
] //Last

1 + x^2 + x^3

$\endgroup$
1
  • $\begingroup$ I think this is correct, and it seems to work. Would you mind explaining the reasoning behind $x^4 -x$ as the modulus? It makes some intuitive sense to me e.g. $x^5/(x^4-x) = x^2$ but I can't quite seem to pin down the reasoning $\endgroup$
    – Kevin
    Aug 11, 2022 at 19:40
2
$\begingroup$

Maybe

p=2;
q=4;
PolynomialMod[x^5 + 6 x^4 + x^3 + 1, p] //. x^k_ :> x^Mod[k, q, 1]

1 + x^2 + x^3.

$\endgroup$
1
  • $\begingroup$ Thank you! I modified it slightly to reduce via the characteristic again after the reduced powers are combined with any other like terms. I also changed the input to the Mod[] function from q to q-1. For multiple variables you can just add another argument specifying the variable to reduce and apply it a second time for that variable: GFReduce[f_, p_, q_, var_] := PolynomialMod[ PolynomialMod[f, p] //. var^k_ :> var^Mod[k, q - 1, 1], p]; $\endgroup$
    – Kevin
    Aug 11, 2022 at 16:15
1
$\begingroup$

There is a built-in function for this PolynomialRemainder.

Examples with constructed remainder:

Block[{f, d, rem, p = 7, q = 4},
 d = x^q - x;
 rem = x^(q - 1) + 1;
 f = (x^2 + 2 x + 5) d + p (x^4 + 5 x + 2) + rem;
 {PolynomialRemainder[f, d, x, Modulus -> p],
  GFReduce[f, p, q, x],
  rem}
 ]
(*  {1 + x^3, 1 + x^3, 1 + x^3}  *)

Block[{f, d, rem, p = 7, q = 4},
 d = x^q - x;
 rem = PolynomialMod[(x + p - 1)^(q - 2) // Expand, p];
 f = (x^2 + 2 x + 5) d + p (x^4 + 5 x + 2) + rem;
 {PolynomialRemainder[f, d, x, Modulus -> p],
  GFReduce[f, p, q, x],
  rem}
 ]
(*  {1 + 5 x + x^2, 1 + 5 x + x^2, 1 + 5 x + x^2}  *)
$\endgroup$
4
  • $\begingroup$ I think the point of the offset (third input into the Mod[]) function is so that x^3 does not reduce to x^0 = 1. That way, $x^{k(q-1)} \rightarrow x^{q-1}$. I think what the offset does is if x%3 = (0,1,2) it shifts it to (3, 1, 2). $\endgroup$
    – Kevin
    Aug 11, 2022 at 19:06
  • $\begingroup$ @Kevin Yes, that's the effect. Somehow I didn't think you wanted that. But it seems you do, right? $\endgroup$
    – Michael E2
    Aug 11, 2022 at 19:27
  • $\begingroup$ Yeah basically I'm just trying to invoke the identity $x^q = x$. $x^{q-1} = x^0$ only if $x \neq 0$, which we don't know for sure, thus $x^{q-1}$ is left alone or $x^{k(q-1)} \rightarrow x^{q-1}$ $\endgroup$
    – Kevin
    Aug 11, 2022 at 19:43
  • $\begingroup$ @Kevin Sorry for not taking $x^q=x$ at face value. I adjusted d to reflect this. $\endgroup$
    – Michael E2
    Aug 11, 2022 at 21:16

Your Answer

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

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