Polynomial GCD over GF(2)

Finding the GCD of 11100 and 10101

Let A = 11100 (x⁴ + x³ + x²) and B = 10101 (x⁴ + x² + 1). We use polynomial long division over GF(2) repeatedly, replacing A with B and B with the remainder R, until B becomes 0.

The final non-zero remainder is 111 (x² + x + 1), which is the greatest common divisor. Its degree is 2. Notice how quotient terms are found by matching the highest degree of the dividend with the divisor.

Explore Polynomial Division

Open the Polynomial GCD over GF(2) explorer. Follow these steps to see the Euclidean algorithm in action:

1. Ensure Polynomial A is set to 10101 and Polynomial B is 1001.
2. Press Step to perform the first division. The trace will show A divided by B, resulting in quotient Q and remainder R.
3. Press Step again to continue the algorithm. The previous divisor becomes the new dividend, and the previous remainder becomes the new divisor.
4. Press Finish to complete all remaining steps instantly. The GCD bits will show 111 and the GCD degree will show 2.
5. Change Polynomial A to 10011 and Polynomial B to 111. Press Finish. The GCD is 1, a constant polynomial with degree 0, indicating they are coprime.
6. Test the boundary case by setting Polynomial A to 0 and Polynomial B to 101. Press Finish. By convention, gcd(0, B) = B, so the GCD is 101.
7. Set both to 0 and press Finish. The GCD bits is 0 and the degree is explicitly "Undefined for zero polynomial".
8. Type an invalid character like "x" in Polynomial A. The trace will immediately clear and show an "Invalid polynomial bits" error.
9. Press Reset to rewind the division trace to step 0 while preserving the entered A and B.

Assumptions and Limitations

This explorer models polynomial arithmetic specifically over the finite field GF(2).

• The module only accepts binary strings consisting of 1s and 0s. The strings represent polynomials up to a certain degree, with leading zeros normalized away.
• The maximum input length is restricted to 9 bits (degree 8). This bounds the maximum number of division steps to 9, keeping the visual trace manageable.
• Empty inputs or strings containing non-binary characters produce an explicit error rather than silently defaulting to zero or producing NaN.
• By mathematical convention, the degree of the zero polynomial is undefined (often denoted as -∞). This module explicitly displays "Undefined for zero polynomial" rather than a numeric 0, which would incorrectly imply a non-zero constant.
• Unlike integer division, GF(2) polynomial long division uses XOR for both addition and subtraction. This tool is not a general integer GCD calculator nor a CRC calculator (which divides a message by a single fixed generator).

Primary Source

The mathematical properties of polynomial rings over finite fields, including GF(2), are a standard topic in abstract algebra.

• SageMath Documentation: Polynomials over GF(2) - Details the computational representation and operations, such as gcd and quotient/remainder division, for binary polynomials. It confirms the bitwise arithmetic model and degree conventions used here.