Polynomial GCD over GF(2)

Polynomials can be represented as binary strings where each bit corresponds to a coefficient in GF(2). The leftmost bit is the most significant, representing the highest degree term. In GF(2), coefficient arithmetic is modulo 2, which means addition and subtraction are identical and equivalent to the bitwise XOR operation. There are no "borrows" or "carries".

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.