0

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:

enter image description here

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).

Community
  • 1
mathmaniage
  • 596
  • 1
    I can't follow your long division. Shouldn't your first step have $5 \cdot 3^{-1}x$ instead of just $x$? The whole point is to try to wipe out the leading term. Part of that is to make the coefficients match. – Randall Jun 20 '19 at 14:02
  • Further, if the divisor $,g,$ has lead coef $,c\neq 1,$ then we can make force it to be $1$ by scaling by $c^{-1}$ then computing $,f/g,$ as $, c^{-1}f/(c^{-1}g),$ which often simplifies the computation. – Bill Dubuque Jun 20 '19 at 14:58
  • "I can't follow your long division...", I'm just matching the coefficient... and If my method is wrong, could you please show me the process of long division by writing below? – mathmaniage Jun 21 '19 at 01:00
  • @mathmaniage The coefficient is 5. You matched the 3. – Randall Jun 22 '19 at 17:16

2 Answers2

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)$.

Ruben
  • 2,082
1

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?

Ingix
  • 14,494
  • @lngix, so how is division performed for polynomials in GF(p)? – mathmaniage Jun 20 '19 at 14:31
  • @lngix, and there's a specific method given for GF(2), but it's not generalized in my text, so I'm wondering if I have done it correctly. – mathmaniage Jun 20 '19 at 14:33
  • and where can I find more about this? I've searched as much as I can, but nothing about this – mathmaniage Jun 20 '19 at 14:35
  • @mathmaniage Your misunderstanding is not division on polynomials, your misunderstanding is on division in GF($p$) itself! You wouldn't ask how to divide $4x^2$ by $2x$ in GF$(5)[x]$, would you? The result is $\frac42x$. When you divide $3x^2$ by $2x$ in GF$(5)[x]$, the result is $\frac32x$, totally analogous. It just so happens that for most people finding the result of the coefficient $\frac42$ in GF$(5)$ is easier than $\frac32$ in GF$(5)$, but both are 'simple' divisions in a field, so not a problem in theory. – Ingix Jun 20 '19 at 15:50