*       0       1       x     x+1     x^2   x^2+1   x^2+x x^2+x+1
      0       0       0       0       0       0       0       0       0
      1       0       1       x     x+1     x^2   x^2+1   x^2+x x^2+x+1 
      x       0       x     x^2   x^2+x   x^2+1 x^2+x+1       1     x+1
    x+1       0     x+1   x^2+x   x^2+1       1       x x^2+x+1     x^2
    x^2       0     x^2   x^2+1       1 x^2+x+1     x+1       x   x^2+x
  x^2+1       0   x^2+1 x^2+x+1       x     x+1   x^2+x     x^2       1
  x^2+x       0   x^2+x       1 x^2+x+1       x     x^2     x+1   x^2+1
x^2+x+1       0 x^2+x+1     x+1     x^2   x^2+x       1   x^2+1       x

#include <Windows.h>
#include <iostream>
#include "MatrixGF2.h"
#include "PolynomialGF2.h"

MatrixGF2<BYTE> g_mtxPositiveBox(16, 16, 0);
MatrixGF2<BYTE> g_mtxReverseBox(16, 16, 0);
MatrixGF2<BYTE> g_mtxBytePositiveTransformMatrix(8, 8, 0);
MatrixGF2<BYTE> g_mtxByteReverseTransformMatrix(8, 8, 0);
BYTE g_bytPositiveFixed = 0;
BYTE g_bytReverseFixed = 0;
PolynomialGF2 g_polyModle;

#define MAKEBYTE(_high, _low) (((_high) << 4) | (_low))

PolynomialGF2 PolynomialEuclidEx(const PolynomialGF2 &kref_polyA,
                                 const PolynomialGF2 &kref_polyB,
                                 PolynomialGF2 &ref_polyX,
                                 PolynomialGF2 &ref_polyY)
{
    if (kref_polyB.EqualZero())
    {
        throw std::runtime_error("The polyB is zero!");
    }

    int iHighestBitIndex = kref_polyA.GetHightestBitIndex();

    PolynomialGF2 polyQuotient(iHighestBitIndex + 1, 0);
    PolynomialGF2 polyRemainder(iHighestBitIndex + 1, 0);
    PolynomialGF2 polyLastLastX(iHighestBitIndex + 1, 0);
    polyLastLastX = 1;
    PolynomialGF2 polyLastLastY(iHighestBitIndex + 1, 0);
    PolynomialGF2 polyLastLastRemainder = kref_polyA;
    PolynomialGF2 polyLastX(iHighestBitIndex + 1, 0);
    PolynomialGF2 polyLastY(iHighestBitIndex + 1, 0);
    polyLastY = 1;
    PolynomialGF2 polyLastRemainder = kref_polyB;

    ref_polyX.Clear();
    ref_polyY.Clear();
    ref_polyX.Insert(0, iHighestBitIndex + 1, 0);
    ref_polyY.Insert(0, iHighestBitIndex + 1, 0);
    ref_polyY = 1;

    do
    {
        polyLastLastRemainder.Division(polyLastRemainder,
                                       polyQuotient,
                                       polyRemainder);
        if (polyRemainder.EqualZero())
        {
            break;
        }

        ref_polyX = polyLastLastX - polyLastX * polyQuotient;
        ref_polyY = polyLastLastY - polyLastY * polyQuotient;

        polyLastLastRemainder = polyLastRemainder;
        polyLastRemainder = polyRemainder;
        polyLastLastX = polyLastX;
        polyLastLastY = polyLastY;
        polyLastX = ref_polyX;
        polyLastY = ref_polyY;
    } while (TRUE);
    return polyLastRemainder;
} //! PolynomialGF2EuclidEx() END

void InitByteTransformMatrix(PolynomialGF2 &ref_polyInit,
                             MatrixGF2<BYTE> &ref_mtxTarget)
{
    size_t uiColumnNumber = ref_mtxTarget.GetColumnNumber();
    if (ref_polyInit.GetSize() != ref_mtxTarget.GetColumnNumber())
    {
        ref_polyInit.PaddingZero(uiColumnNumber);
    }

    size_t uiRowNumber = uiColumnNumber;
    for (size_t cntY = 0; cntY < uiRowNumber; cntY++)
    {
        size_t iOffset = cntY;
        for (size_t cntX = 0; cntX < uiColumnNumber; cntX++)
        {
            size_t iActualPos = cntX + iOffset;
            if (iActualPos >= uiColumnNumber)
            {
                iActualPos -= uiColumnNumber;
            }
            ref_mtxTarget[cntY][iActualPos] = ref_polyInit[cntX];
        }
    }
} //! InitByteTransformMatrix() END

void InitPositiveBox()
{
    MatrixGF2<BYTE> mtxFixed = PolynomialGF2(g_bytPositiveFixed).GetDequeFormat();

    for (size_t cntY = 0; cntY < 16; cntY++)
    {
        for (size_t cntX = 0; cntX < 16; cntX++)
        {
            BYTE bytSource = (BYTE)MAKEBYTE(cntY, cntX);
            if (0 == bytSource)
            {
                g_mtxPositiveBox[cntY][cntX] = g_bytPositiveFixed;
                continue;
            }

            PolynomialGF2 polyInverseElement;
            PolynomialGF2 polyX;
            PolynomialGF2 polySource = bytSource;

            // 求乘法逆元
            if (!polySource.EqualZero())
            {
                PolynomialGF2 polyResult =
                    PolynomialEuclidEx(g_polyModle,
                                       polySource,
                                       polyX,
                                       polyInverseElement);
            }
            else
            {
                polyInverseElement = { 0 };
            }
            polyInverseElement.ClearInvalidZero();
            MatrixGF2<BYTE> mtxValue = polyInverseElement.GetDequeFormat();

            mtxValue.PaddingRow(
                g_mtxBytePositiveTransformMatrix.GetColumnNumber()
            );
            mtxFixed.PaddingRow(mtxValue.GetRowNumber());

            mtxValue = g_mtxBytePositiveTransformMatrix * mtxValue + mtxFixed;
            g_mtxPositiveBox[cntY][cntX] =
                (BYTE)PolynomialGF2(mtxValue.Transform2Vector()).ToNumber();
        }
    }
} //! InitPositiveBox() END

void InitReverseBox()
{
    MatrixGF2<BYTE> mtxFixed = PolynomialGF2(g_bytReverseFixed).GetDequeFormat();

    for (size_t cntY = 0; cntY < 16; cntY++)
    {
        for (size_t cntX = 0; cntX < 16; cntX++)
        {
            BYTE bytSource = (BYTE)MAKEBYTE(cntY, cntX);
            MatrixGF2<BYTE> mtxValue = bytSource;
            int iValueColumnNumber =
                g_mtxByteReverseTransformMatrix.GetColumnNumber();
            if (0 == bytSource)
            {
                mtxValue.InsertRow(0, iValueColumnNumber, 1, 0);
            }
            mtxValue.PaddingRow(iValueColumnNumber);
            mtxFixed.PaddingRow(mtxValue.GetRowNumber());
            mtxValue = g_mtxByteReverseTransformMatrix * mtxValue + mtxFixed;

            PolynomialGF2 polyInverseElement;
            PolynomialGF2 polyX;
            PolynomialGF2 polyValue = mtxValue.Transform2Vector();

            if (!polyValue.EqualZero())
            {
                // 求乘法逆元
                PolynomialGF2 polyResult =
                    PolynomialEuclidEx(g_polyModle,
                                       polyValue,
                                       polyX,
                                       polyInverseElement);
            }
            else
            {
                polyInverseElement = { 0 };
            }

            g_mtxReverseBox[cntY][cntX] = (BYTE)polyInverseElement.ToNumber();
        }
    }
} //! InitReverseBox() END

void InitStandardBox()
{
    g_polyModle = { 1, 1, 0, 1, 1, 0, 0, 0, 1 };
    PolynomialGF2 polyPositiveSeed = { 1, 0, 0, 0, 1, 1, 1, 1 };
    InitByteTransformMatrix(polyPositiveSeed, g_mtxBytePositiveTransformMatrix);
    PolynomialGF2 polyReverseSeed = { 0, 0, 1, 0, 0, 1, 0, 1 };
    InitByteTransformMatrix(polyReverseSeed, g_mtxByteReverseTransformMatrix);

    g_bytPositiveFixed = 0x63;
    g_bytReverseFixed = 0x05;
    InitPositiveBox();
    InitReverseBox();
    printf("Positive box: \n%s\n",
           g_mtxPositiveBox.GetWrittenFormat().c_str());
    printf("Reverse box: \n%s\n",
           g_mtxReverseBox.GetWrittenFormat().c_str());
} //! InitStandardBox() END

int main()
{
    InitStandardBox();
    system("pause");
    return 0;
}

2.4. 欧几里得算法

INT64 EuclidEx(INT64 i64A, INT64 i64B, INT64 &ref_i64X, INT64 &ref_i64Y)
{
    if (0 == i64B)
    {
        return 0;
    }

    INT64 i64Quotient = 0;
    INT64 i64LastLastX = 1;
    INT64 i64LastLastY = 0;
    INT64 i64LastX = 0;
    INT64 i64LastY = 1;
    INT64 i64LastLastRemainder = i64A;
    INT64 i64LastRemainder = i64B;
    INT64 i64Remainder = 0;
    ref_i64X = 0;
    ref_i64Y = 1;

    do
    {
        i64Quotient = i64LastLastRemainder / i64LastRemainder;
        i64Remainder = i64LastLastRemainder % i64LastRemainder;
        if (0 == i64Remainder)
        {
            break;
        }

        ref_i64X = i64LastLastX - i64LastX * i64Quotient;
        ref_i64Y = i64LastLastY - i64LastY * i64Quotient;

        i64LastLastRemainder = i64LastRemainder;
        i64LastRemainder = i64Remainder;
        i64LastLastX = i64LastX;
        i64LastX = ref_i64X;
        i64LastLastY = i64LastY;
        i64LastY = ref_i64Y;
    } while (TRUE);

    return i64LastRemainder;
} //! EuclidEx() END

int main()
{
    INT64 i64X = 0;
    INT64 i64Y = 0;
    INT64 i64Result = EuclidEx(1759, 550, i64X, i64Y);

    printf("Result: %I64d\n", i64Result);
    printf("X: %I64d\n", i64X);
    printf("Y: %I64d\n", i64Y);

    system("pause");

    return 0;
}

INT64 EuclidEx(INT64 i64A, INT64 i64B, INT64 &ref_i64X, INT64 &ref_i64Y)
{
    if (0 == i64B)
    {
        return 0;
    }

    INT64 i64Quotient = 0;
    INT64 i64LastLastX = 1;
    INT64 i64LastLastY = 0;
    INT64 i64LastX = 0;
    INT64 i64LastY = 1;
    INT64 i64LastLastRemainder = i64A;
    INT64 i64LastRemainder = i64B;
    INT64 i64Remainder = 0;
    ref_i64X = 0;
    ref_i64Y = 1;

    do
    {
        i64Quotient = i64LastLastRemainder / i64LastRemainder;
        i64Remainder = i64LastLastRemainder % i64LastRemainder;
        if (0 == i64Remainder)
        {
            break;
        }

        ref_i64X = i64LastLastX - i64LastX * i64Quotient;
        ref_i64Y = i64LastLastY - i64LastY * i64Quotient;

        i64LastLastRemainder = i64LastRemainder;
        i64LastRemainder = i64Remainder;
        i64LastLastX = i64LastX;
        i64LastX = ref_i64X;
        i64LastLastY = i64LastY;
        i64LastY = ref_i64Y;
    } while (TRUE);

    return i64LastRemainder;
} //! EuclidEx() END

int main()
{
    INT64 i64X = 0;
    INT64 i64Y = 0;
    INT64 i64Result = EuclidEx(1759, 550, i64X, i64Y);

    printf("Result: %I64d\n", i64Result);
    printf("X: %I64d\n", i64X);
    printf("Y: %I64d\n", i64Y);

    system("pause");

    return 0;
}