You will create a Visual C++ program that lets you add, subtract. multiply. or divide two elements of a Galois field with fewer than 50 elements. Again, for the user-interface parts of the program, you need only follow instructions, but you will have to implement the "real mathematics" of arithmetic in finite fields yourself.

The program used in class that does this, "GField.exe", can be downloaded from the course Web site.  You can also download a copy of this document, from which you can paste code into your project as you are creating it. 

1. Click the "Microsoft Visual C++ 6.0" icon on the desktop, or go to Start...Programs...Microsoft Visual C++ 6.0...Microsoft Visual C++ 6.0 if there is no icon on the desktop.  From the menu select File...New.  Click on the Projects tab, then click on MFC AppWizard(exe).  In the location box, choose the folder in which you keep your Math S15 projects. As the project name, type in GField..  Now click OK to start   the AppWizard.

2. In Step 1, select Dialog Based, then click Next.
       In Step 2, uncheck About Box and ActiveX Controls. Change  the title to "Galois Field Calculator."  Click Finish.

3. Go to "Resource View" and  click on the + next to Dialog, then double-click on IDD_GFIELD_DIALOG.   Click on the text that starts "TODO:...", then press the Delete key to get  rid of it.  Do the same for the Cancel button.  With the OK button  highlighted, press the Enter key.  Under the General tab, edit the caption  to change it to "Done."  Click the little "x" to finish, then drag the  button down to the lower right-hand corner of the dialog.

4. Now we will change some properties of the entire dialog.  Click anywhere in empty space on the dialog, then press Enter.
    Under the General tab, click Font...and select Courier New, Size 10.
    Under the Styles tab, check Minimize box.
    Click the little x to close Dialog Properties.

5. In order to be able to switch among different Galois fields, we are going to embed a property sheet with two tabbed property pages in our dialog.  Later we can add more pages to support additional Galois fields.  This is not supported by the graphical dialog editor, but it is not hard to do.  We begin by making the two pages.  While still in Resource View, right-click on Dialog and select Insert... from the menu that pops up.  Under Insert Resource, click the + next to Dialog, then select IDD_OLE_PROPPAGE_MEDIUM and click New.  Delete the TODO... item, then press Enter to get to the Dialog Properties.  Under the General tab, change the ID to IDD_ORDER3 and the caption to Order 3.  Since there will be only a few buttons, click Font... and change the Font to Courier New, size 10. (Note: if you decide later to do the 49-element field, leave the font size as 8 on that property page).
On the dialog place three buttons:
ID IDC_3_0    Caption [0]
ID IDC_3_1    Caption [1]
ID IDC_3_2    Caption [2]
Now press Ctrl-W to bring up ClassWizard.  You will be invited to "Create a new class." Press OK to do so.  For the name choose COrder3, and for the Base Class change CDialog to CPropertyPage.  With the Class Name now showing COrder3, add three member variables
For IDC_3_0,    CButton m_3_0
For IDC_3_1,    CButton m_3_1
For IDC_3_2,    CButton m_3_2
Under the Message Maps tab, add a BN_CLICKED handler for each of the three buttons.
Finally, with the class name COrder3 highlighted under Object IDs, scroll down under Messages to OnSetActive and click Add Function to override the virtual function OnSetActive(), which gets called whenever this page is selected.  Click OK to exit from Class View.
Right-click on the class COrder3 and add two member variables:
   CGFieldDlg* m_pDlg;
   CFiniteField* m_pField;
Just above the comment
//  COrder 3 dialog, add the declarations
class CGFieldDlg;
class CFiniteField;
These will keep the compiler happy when it sees the pointer-type variables that you just declared.  Use Ctrl-X to delete the line
#include "GFieldDlg.h"    //Added by Class View
and then paste this line at the top of Order3.cpp

6. Repeat the operations of step 5 to add a property page IDD_ORDER5 with an associated class COrder5 derived from CPropertyPage. This should have with 5 buttons, each with its own member variable, starting with
IDC_5_0     Caption [0]      CButton m_5_0
and ending with
IDC_5_4     Caption [4]      CButton m_5_4
(In general, there is no required order for the buttons, but it is convenient to have their IDs end in 0, 1, 2, ...)
Again add BN_CLICKED handlers for the buttons and override OnSetActive.
Right-click on the class COrder5 and add two member variables:
   CGFieldDlg* m_pDlg;
   CFiniteField* m_pField;
Just above the comment
  //  COrder 5 dialog,
add the declarations
class CGFieldDlg;
class CFiniteField;
Near the top of Order5.cpp, insert the line
#include "GFieldDlg.h"

7. Go into ClassView. Right-click on CGFieldDlg and add a member variable
CPropertySheet   m_propSheet
Also add a member variable
COrder3 m_page3
and a member variable
COrder5 m_page5
At the top of  the file GFieldDlg.h will be the line
#include "Order3.h"  // Added by ClassView
Under it, add the line
#include "Order5.h"

Also add a member function
void InitPropertySheet
Type in (or paste in from this document) this code:
   m_page3.m_pDlg = this;
   m_page3.m_pField = &m_field;
   m_page5.m_pDlg = this;
   m_page5.m_pField = &m_field;
   m_propSheet.AddPage(&m_page3);
   m_propSheet.AddPage(&m_page5);
   m_propSheet.Create(this, WS_CHILD | WS_VISIBLE, 0);
   m_propSheet.SetWindowPos(NULL,0,0,0,0,SWP_NOSIZE | SWP_NOZORDER);

In the function CGFieldDlg::OnInitDialog add, just before the last line,
InitPropertySheet();

8. Finally, right-click on GFieldClasses in ClassView and select New Class... from the menu.
Choose Generic Class as the Class type and CFiniteField as the name.
This class will contain nothing but mathematics, and once it is finished, you will be able to use it in other projects.
In CGFieldDlg add a member variable
CFiniteField m_field;
Now press Ctrl-F5 to build and run the project.  If you have followed instructions very carefully, you will see two tabs with captions Order 3 and Order 5 at the upper left of the dialog, and clicking these tabs will let you switch between the two property pages.  Later, when you want to add and display property pages for other Galois fields, refer to steps 5 through 7 to remind yourself about how to add them.  The tabs always appear, from left to right, in the order specified by the calls to AddPage() in InitPropertySheet().

At this point you have completed the hard work of defining all the C++ classes in the project and making it possible for them to communicate with one another.  It is prudent now to close the GField workspace and reopen it in order to make sure that the changes you have made to the project workspace are safely stored in files.

9.  Now go back to ResourceView and open up IDD_GFIELD_DIALOG.  To the right of where the property pages will display, add a column of five buttons as follows:

IDC_PLUS    Caption +
IDC_MINUS  Caption -
IDC_TIMES   Caption *
IDC_SLASH   Caption /
IDC_EQUALS  Caption =

Across the bottom of the dialog , add a row of read-only edit boxes, as follows:
IDC_LEFT
IDC_OP
IDC_RIGHT
IDC_RESULT
For each of these, go to the Styles tab to check Read-only, and also change Align text to Centered.
Now bring up Class Wizard (with CGFieldDlg as the Class name).  Add BN_CLICKED handlers for the five buttons.  For the four edit boxes, add CString member variables m_left, m_right, m_op, and m_result.  Build and run the project to make sure that the property pages do not overlap with any of the controls that you just added.

10. Now the dialog class must be made aware of the buttons on the active property page.  At the top of the file CGFieldDlg.h, above the class declaration, add three lines

#define MAX_ORDER 50
enum stateEnum  {STATE_LEFT, STATE_OP, STATE_RIGHT};
enum opEnum  {OP_ADD, OP_SUBTRACT, OP_MULTIPLY, OP_DIVIDE};

Then add the member variables
    opEnum m_enumOp;
   CButton* m_pButtons[MAX_ORDER];
   stateEnum m_state;

and the member functions

   void ExecuteButton(int n);
   void Reinitialize();

11. In the class CFiniteField add member variables that specify the elements of the finite field:

   int m_prime;  //the size of the field from which the coefficient are taken
   int m_power;  //the maximum number of terms in a polynomial
   int m_nElements;  //the number of  elements ("prime" raised to "power")
   CStringArray m_strElements;  //the array of polynomials that specify the elements

and the member function
   void Initialize(int prime, int power);
 

For COrder3, m_prime is 3 and m_power is 1.
The polynomials have just 1 term; they are [0] through [2]
COrder5 is similar.
But when you do COrder4, m_prime is 2 and m_power is 2
The polynomials have 2 terms: they are [0], [1], [x], and [x+1]
If you do COrder27 (ambitious), m_prime = 3 and m_power = 3.
You will then have polynomials like [2x2 + x + 2]

12. Whenever a property page becomes active, CGFieldDlg must get pointers to all the buttons on the page, while CFiniteField must be informed about the captions on the buttons, which specify the elements of the field.  This is done in OnSetActive.  For COrder3 you need

BOOL COrder3::OnSetActive()
{
   m_pField->Initialize(3,1);
   m_pDlg->m_pButtons[0] = &m_3_0;
   m_pDlg->m_pButtons[1] = &m_3_1;
   m_pDlg->m_pButtons[2] = &m_3_2;
   m_pDlg->Reinitialize();
   return CPropertyPage::OnSetActive();
}

while for COrder5 you will want
BOOL COrder5::OnSetActive()
{
   m_pField->Initialize(5,1);
   m_pDlg->m_pButtons[0] = &m_5_0;
   m_pDlg->m_pButtons[1] = &m_5_1;
   m_pDlg->m_pButtons[2] = &m_5_2;
   m_pDlg->m_pButtons[3] = &m_5_3;
   m_pDlg->m_pButtons[3] = &m_5_4;
   m_pDlg->Reinitialize();
   return CPropertyPage::OnSetActive();
}

  As you add other Galois fields, it is easy to modify a copy of one of these functions to do the right thing in the class for the new field.

13. Now add the code for Initialize, which calculates the number of elements as follows:
void CFiniteField::Initialize(int prime, int power)
{
   m_prime = prime;
   m_power = power;
   m_nElements = prime;
   while (--power) {
       m_nElements *= prime;
   }
}

In class CGFieldDlg, add the code for Reinitialize, which sets up the array of polynomial strings for the field elements by reading the captions of the buttons on the property page.

void CGFieldDlg::Reinitialize()
{
   CString text;
   m_field.m_strElements.RemoveAll();
   for (int i = 0; i < m_field.m_nElements; i++) {
       m_pButtons[i]->GetWindowText(text);
       m_field.m_strElements.Add(text);
   }
   m_left.Empty();
   m_right.Empty();
   m_op.Empty();
   m_result.Empty();
   m_state = STATE_LEFT;
}

14. The function ExecuteButton does different things depending on the state of the calculation: sometime the element is the left operand and sometime it is the right operand.

void CGFieldDlg::ExecuteButton(int n)
{
   switch (m_state) {
   case STATE_LEFT:
       m_left = m_field.m_strElements[n];
       m_right = "";
       m_result = "";
       m_op = "";
       m_state = STATE_OP;
       break;
   case STATE_OP:
       m_left = m_field.m_strElements[n];
       m_result = m_field.m_strElements[n];
       break;
   case STATE_RIGHT:
       m_right = m_field.m_strElements[n];
       break;
   default:
       break;
   }
   UpdateData(FALSE);
}

15. Each button on each property page simply calls ExecuteButton with the correct argument:
void COrder3::On30()
{
   m_pDlg->ExecuteButton(0);
}

void COrder3::On31()
{
   m_pDlg->ExecuteButton(1);
}

void COrder3::On32()
{
   m_pDlg->ExecuteButton(2);
}

You must also add the similar functions for COrder5

16. The buttons for the arithmetic operations just record what operation is desired and change the state:

void CGFieldDlg::OnMinus()
{
   if (m_state == STATE_OP) {
       m_op = "-";
       m_enumOp = OP_SUBTRACT;
       m_state = STATE_RIGHT;
       UpdateData(FALSE);
   }
}

void CGFieldDlg::OnPlus()
{
   if (m_state == STATE_OP) {
       m_op = "+";
       m_enumOp = OP_ADD;
       m_state = STATE_RIGHT;
       UpdateData(FALSE);
   }
}

void CGFieldDlg::OnSlash()
{
   if (m_state == STATE_OP) {
       m_op = "/";
       m_enumOp = OP_DIVIDE;
       m_state = STATE_RIGHT;
       UpdateData(FALSE);
   }
}

void CGFieldDlg::OnTimes()
{
   if (m_state == STATE_OP) {
       m_op = "*";
       m_enumOp = OP_MULTIPLY;
       m_state = STATE_RIGHT;
       UpdateData(FALSE);
   }
}
17. At this point everything should be working except the equals button.  When you run the program, you can push a field element button, then an operation, then another field element button, and the "arithmetic problem" should appear at the bottom of the dialog.
 

18. When the equals button is pressed the CFiniteField class should take the strings for the two operands, perform the correct arithmetic, and display the result, as follows:

void CGFieldDlg::OnEquals()
{
   switch(m_enumOp) {
   case OP_ADD:
       m_result = m_field.Add(m_left, m_right);
       break;
   case OP_SUBTRACT:
       m_result = m_field.Subtract(m_left, m_right);
       break;
   case OP_MULTIPLY:
       m_result = m_field.Multiply(m_left, m_right);
       break;
   case OP_DIVIDE:
       m_result = m_field.Divide(m_left, m_right);
       break;
   default:
       break;
   }
   m_state = STATE_LEFT;
   UpdateData(FALSE);
}

To finish the job, you need to add four functions to CFiniteField, and in fact it is useful to define six functions. Use AddMemberFunction to add these:
   CString Invert(CString op);
  CString Negate(CString op);
   CString Add(CString op1, CString op2);
   CString Subtract(CString op1, CString op2);
   CString Multiply(CString op1, CString op2);
   CString Divide(CString op1, CString op2);
 

As long as m_power is 1, the arithmetic is easy.  Here are some functions that do the job.

CString CFiniteField::Add(CString op1, CString op2)
{
   int n1 = op1[1] - '0';
   int n2 = op2[1] - '0';
   int n3 = (n1 + n2) % m_prime;
   return CString("[") + char(n3+'0') + "]";
}

CString CFiniteField::Subtract(CString op1, CString op2)
{
   return Add(op1, Negate(op2));
}

CString CFiniteField::Multiply(CString op1, CString op2)
{
   int n1 = op1[1] - '0';
   int n2 = op2[1] - '0';
   int n3 = (n1 * n2) % m_prime;
   return CString("[") + char(n3+'0') + "]";
}

CString CFiniteField::Divide(CString op1, CString op2)
{
   return Multiply(op1, Invert(op2));
}

CString CFiniteField::Negate(CString op)
{
   int n1 = op[1] - '0';
   int n2 = (- n1) % m_prime;
   return CString("[") + char(n2+'0') + "]";
}

CString CFiniteField::Invert(CString op)
{
   for (int i = 0; i < m_nElements; i++) {
       if (Multiply(op, m_strElements[i]) == "[1]")
           return m_strElements[i];
   }
//If we got here it was probably division by zero
   ASSERT(FALSE);
   return ("[0]");
}

19. Your job is to make this application work for the more challenging cases where the number of elements in the field is a power of a prime number.  With a limit of 49 elements (only because you can't get more buttons onto a property page of the size that we have used), some interesting possibilities are
4, 9, 25, 49 for m_power = 2
8, 27  for m_power = 3
16 for m_power = 4
32 for m_power = 5.
When m_power is greater than 1, you need to "simplify" the result of polynomial multiplication by taking the result modulo an irreducible polynomial.  Here are some good choices.
According to the book in which I found these polynomials (Lidl and Pilz, Applied Abstract Algebra), for these choices x is a "primitive element:" that is, every nonzero element of the field is a power of x.

If m_prime = 2
m_power = 2:   x2 + x + 1 = 0    so replace x2 by -x -1(which is the same as x + 1)
m_power = 3:   x3 + x + 1 = 0    so replace x3 by -x -1(which is the same as x + 1)
m_power = 4:   x4 + x + 1 = 0    so replace x4 by -x -1(which is the same as x + 1)
m_power = 5:   x5 + x2 + 1 = 0    so replace x5 by -x2 -1(which is the same as x2 + 1)

If m_prime = 3
m_power = 2:   x2 + 2x + 2 = 0    so replace x2 by -2x - 2 (which is the same as x + 1)
m_power = 3:   x3 + 2x + 1 = 0    so replace x3 by -2x -1(which is the same as x + 2)

If m_prime = 5
m_power = 2:   x2 + 3x + 3 = 0    so replace x2 by -3x -3 (which is the same as 2x + 2)

If m_prime = 7
m_power = 2:   x2 + x + 3 = 0    so replace x2 by -x -3 (which is the same as 6x + 4)

A good general strategy is to write a function that turns a CString into an array of coefficients, functions to add and multiply the polynomials that these arrays represent, and a function to convert an array of coefficients back into a button caption.

Grading standards:
Getting GF[3] and GF[5] to work (just following the instructions) 5 points
Also getting GF[7]  to work (m_power = 1) : 6 points
Also getting GF[4]  to work (m_power = 2, but you can hard-code each case) : 7 points
Also GF[9]  to work (m_power = 2)  : 8 points
For the next two the polynomial muliplication starts to get hard
Also getting GF[8]  to work (m_power = 3)  : 9 points
At this point you have done all the cases that are posted on the course Web site
Also getting GF[16] (m_power = 4) to work  10 points
The following don't really look worth the effort, but if you're having fun, keep going:
Also getting GF[25](m_prime = 5)  to work 11 points
Also getting GF[27](m_prime = 3, m_power = 3)  to work 12 points
Also getting GF[49](m_prime = 7)  to work 13 points
Also getting GF[32](m_power = 5)  to work 14 points
(There will be a limit of 40 points for all 4 programming exercises in the course, however)