performing division and multiplication over GF(p)

Question

Considering a simple example:

$$\frac{5x^2}{3x}\ \ \ \ \ over\ GF(7)$$ one way to do it would be:

$$\frac{5}{3} x$$ $$\Rightarrow 5 \times 3^{-1}x$$ $$\Rightarrow 4x$$

But, I tried performing long division performing long division goes like this:

Is this the correct way to perform long division over GF(p)?

And during multiplication of two polynomials with coefficients over GF(p), can the resultant polynomial reach any order or is it reduced via some irreducible polynomial like in GF(p^n)?

There are limited resources that demonstrate division over GF(p).

Answer 1

I believe the definition of $GF(p)$ is that it is the finite field of order $p$. In particular this is a field, so it has no zero divisors. So if I multiply two polynomials then the degree of the product is going to be the sum of the individual degrees.

I think you may be confused with the polynomial used to define $GF(p^n)$ in some literature. In particular the finite field $GF(p)$ for $p$ prime is easy to visualize, as this is just $\mathbb Z / n \mathbb Z$. Then usually to define $GF(p^n)$ one takes a degree $n$ irreducible monic polynomial $f$ in $GF(p)[X]$, so that $GF(p^n) \simeq GF(p)[X] / (f)$. This polynomial $f$ has nothing to do with polynomials with coefficients in $GF(p^n)$.

Answer 2

Long division is based on the concept of division with remainder. You have the 'big' thing that you want to divide by the 'small thing', and you do that 'as much as possible', then deal with the remainder until the remainder becomes $0$.

That concept doesn't apply to GF($p$), at least not in a non-trivial manner. Every element of it is divisible by any other (except $0$), so there are no remainders $\neq 0$. You can and have to divide 5 by 3, as there is no remainder. Figuring out that the result is $4$ is a 'technical' matter just as finding out what $\frac{42}7$ is, for example.

OTOH, as can be seen, you get the correct result. That's because you are correctly calculating $5x^2-3x(x+x+2x)$, which is $0$ in GF($7$)[x]. But you don't have a deterministic algorithm that guarantees you that you end at some time, because there is no reasonable rule that says when your remainder is $2x^2$ you have to multply with $x$ to get $3x^2$! Why $2x$ and not $3x$ or $4x$ or whatever?