Mathematics 152
Programming Project #2
A KDE C++ Calculator for Galois Fields

Revised: December 1, 2003

You will create a 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.

If you get errors while building the project, press F4 to see the offending line and try to fix it.  If the source of the error is not obvious, it might be simplest to delete the project directory and start over.  Once you have completed this part of the project build process, you will have a makefile that does all the tricky parts of the build automatically, and adding functionality to the application will be straightforward.

1. Click the KDevelop icon and close the "Tip of the Day."  From the main menu, select Project...New.  The Application Wizard drops down.  In the tree on the left, click the + next to KDE, then click KDE 2 Mini from the list that drops down. Click the Next Button.

2. Now you see the Generate Settings dialog.  For a project directory, navigate to a subdirectory of your home directory, and within this choose a new subdirectory named "proj_gf"  An example project directory might be /home/paulb/S45/homework/proj_gf.  Enter GF as the project name.  The Author and Email fields should have been filled in automatically from when you configured KDevelop. Below, uncheck everything except "generate sources and headers."  Click Create.  Wait until you see the "READY" message, then click Exit.  At the top of the left panel, click the Classes tab.  You will see a class GF.

3. Select File...New from the menu or click the New icon at the left of the toolbar, and choose Qt Designer File (.ui).  Type in "gfbase" as the filename; the .ui will be added automatically.  Leaving "use Template" and "add to Project" checked, click OK.  Respond "No" to "Do you want to load it as ASCII file?"  When the New Form dialog pops up, choose Widget and click OK.  Under Properties, change the name from Form1 to GFBase.  Use File...SaveAs.. to save the form, and be sure to navigate down to the directory named gf under your project, for example /home/paulb/S15/homework/proj_gf/gf.  You should already see gfbase in this directory -- overwrite it.  Close Qt Designer.

4. Select Build..Make (or press F8) to build the project.  After a while you will see the message ***success***.  Select Project...Add Existing Files....  For source files, navigate down to the gf directory and select the file gfbase.h, which was created during the build process.  Do not also select gfbase.cpp, or you will get linker errors! Click OK twice. Now you should see GFBase under the Classes tab, along with GF.  You should regard the class GFBase as "read-only" since it will be rebuilt every time you edit gfbase.ui, and any changes that you made would be lost.  When the file gfbase.h is rebuilt, you will need to reload it into the editor.  You may be asked about this when you right-click on GFBase.

5. Right click the GF class and choose Goto declaration.  Change the first line to
class GF: public GFBase.
Above this, change
#include <qwidget.h>
to
#include "gfbase.h"

6. Click the + next to GF, and click the constructor.
Replace the second occurrence of QWidget by GFBase to get
GF::GF(QWidget *parent, const char *name) : GFBase(parent, name).
Press F8 to rebuild the project, and you should see *** success ***
When you press F9, the project should run, showing you a blank form.

7. Continue by adding widgets to the form.  An easy way to do this is to select Tools...Qt Designer, then choose File... Recently opened files.  Your file gfbase.ui will be at the bottom of the list.  Alternatively, under the Files tab, you can double-click gfbase.ui and answer No to "Do you want to load it as ASCII file?"
When the widget editor displays the widget, use the properties pane on the left to change the caption to Galois Field Calculator. (If there are other panes to the left of the properties pane, you may just want to get rid of them in order to leave lots of room on the right for the widget itself.

8. To get this widget started, place a large Tab Widget (icon is three to the right of the Group Box) across the top of the main widget. Leave about 100 pixels free at the bottom. Change its name to TabWidgetMain. For the left tab, change the page Title to Order 3 and the page Name to Order3.  Click on the right(second) tab, and change the page Title to Order 5 and the page Name to Order5.  Right-click on the tab widget, choose Add Page, and change the page Title to Order 27 and the page Name to Order27. Notice that you can select a tab by holding down the left mouse button and drag it into a new position.  You will need to do this later for Order 4, which should go between Order 3 and Order 5.
Close Qt Designer, and rebuild the project to see that you can switch among tabs on the main widget.

9. The next step is to create a custom widget, a button that has all the properties of an element of a Galois field and that can display the element as a polynomial.
Begin by selecting Project...New Class... from the menu.  As the Classname, choose GFButton; as the Baseclass choose QPushButton.  The file names will be set appropriately, but you must also check "generate a QWidget-childclass."  Then click OK.

Open up gfbase.ui in Qt Designer.  Choose Tools...Custom...Edit Custom Widgets... from the main menu, and click New Widget. As Class, type in GFButton; as Headerfile enter gfbutton.h.  For Size Hint, select 60 on the left(width) and 30 on the right (height).
Click the Properties tab, and add the following seven properties by using the New Properties button
Property name c0, type Int
Property name c1, type Int
Property name c2, type Int
Property name c3, type Int
Property name c4, type Int
Property name power, type Int
Property name prime, type Int
These let you set the properties of a GFButton in Qt Designer.
Click the Signals tab, and use the New Signal button to add
clicked(int, int, int, int, int)
This will let the button send the five coefficients of the polynomial associated with it to a slot.
Click Close to close the custom widget editor.

10. Make sure that the Order 3 tab is selected.  Choose the GFButton icon from the bottom row of toolbars (or use Tools...Custom...GFButton from the main menu) and drag a GFButton onto the tab widget.  In the properties, change prime to 3 and power to 1.  Change the name to GFButton1.  Now, with this button selected, press Ctrl-C and Ctrl-V to make a copy.  Drag the copy below the original button.   For the copy, change the property c0 to 1.  The generated name is OK.
Make yet another copy, and change the property c0 to 1.

11. Click the Order 27 tab.  Add one button, whose purpose at the moment is to test the ability to paint exponents correctly.
This button should have c1 = 2, c2 = 1, power = 3, prime = 3 (the other properties are OK as 0).
Close Qt Designer.

12. Open up the file gfbutton.h.  Immediately under Q_OBJECT, add the following macros, which give access to the properties of the buttons.
   Q_PROPERTY(int c0 READ getc0  WRITE setc0)
   Q_PROPERTY(int c1 READ getc1  WRITE setc1)
   Q_PROPERTY(int c2 READ getc2  WRITE setc2)
   Q_PROPERTY(int c3 READ getc3  WRITE setc3)
   Q_PROPERTY(int c4 READ getc4  WRITE setc4)
   Q_PROPERTY(int prime READ getprime WRITE setprime)
   Q_PROPERTY(int power READ getpower WRITE setpower)

Then, in the class GFButton, right-click and select Add Member Variable
Start with Type int, Name c), and under Properties, Read and Write both checked.
Notice that new functions getc0() and setc0() appear.
Repeat for the other six properties.
In the constructor for GFButton, initialize all the coefficients to zero:
GFButton::GFButton(QWidget *parent, const char *name ) : QPushButton(parent,name) {
  setc0(0);
  setc1(0);
  setc2(0);
  setc3(0);
  setc4(0);
}
Finally, to work around what may be a bug is the current version of Qt, you must open up gfbutton.h
and change
   virtual const int& getc0();
to
   virtual const int& getc0() const;
Repeat for the other six properties.
In gfbutton.cpp, change
   const int& GaloisButton::getc0(){
to
  const int& GaloisButton::getc0() const{
Repeat for the other six properties.

13. Now open up the constructor for the class GF and add the following to cause the tag <x> to draw an exponent.
   QStyleSheet* myStyleSheet =   QStyleSheet::defaultSheet();
  QStyleSheetItem* item = new QStyleSheetItem(myStyleSheet, "x");
  item->setVerticalAlignment(QStyleSheetItem::VAlignSuper);
  QStyleSheet::setDefaultSheet(myStyleSheet);

Then, in class GFButton, add this member function.
QString GaloisButton::makeText(int c0, int c1, int c2, int c3, int c4){
  QString text = "[";
  if (c4 > 1)
     text += QString("%1").arg(c4);
  if (c4 > 0)
     text += "x<x>4</x>+";
  if (c3> 1)
     text += QString("%1").arg(c3);
  if (c3> 0)
     text += "x<x>3</x>+";
  if (c2 > 1)
     text += QString("%1").arg(c2);
  if (c2 > 0)
     text += "x<x>2</x>+";
  if (c1 > 1)
     text += QString("%1").arg(c1);
  if (c1 > 0)
     text += "x+";
  if(text == "["  || (c0 > 0))
       text +=  QString("%1").arg(c0);
  text.stripWhiteSpace();
  if (text.right(1) == "+")
       text = text.left(text.length()-1);
  return text+"]";
}
This takes the coefficients of a polynomial whose degree is 4 or less and creates a string which, when interpreted as "rich text," will draw the usual representation of the polynomial.  Coefficients and exponents of 1 are not shown, and any term whose coefficient is 0 does not appear at all.

14. Add this override of the virtual function paintEvent to paint the text in the center of the button.
void GFButton::paintEvent(QPaintEvent* e){
  QPushButton::paintEvent(e);
  QPainter p(this);
  QRect textRect = rect();
  QSimpleRichText richText(makeText(c0,c1,c2,c3,c4), QFont("lucidatypewriter"));
  int w = richText.widthUsed();
  int h = richText.height();
  int wspace = (textRect.width()-w) /2;
  int hspace = (textRect.height()-h) /2;
  if (isDown())
   richText.draw(&p,textRect.left()+wspace+1,textRect.top()+hspace+1,textRect,colorGroup());
  else
   richText.draw(&p,textRect.left()+wspace,textRect.top()+hspace,textRect,colorGroup());
}

Finally, add this function so that a signal is emitted when the button is clicked

void GaloisButton::mousePressEvent(QMouseEvent* e){
  emit clicked(c0,c1,c2,c3,c4);
}

At the top of gfbutton.cpp
#include <qpainter.h>
#include <qsimplerichtext.h>

At the top of gf.cpp
#include <qstylesheet.h>
#include <qtabwidget.h>
#include <qlabel.h>

At this point you can build and run the project.  On the Order 3 tab, you should see buttons whose captions are [0], [1], and [2].
On the order 27 tab should be [x2 +2x].

15. To complete the GFButton class, right-click the class name, select Add Signal, and add
clicked(int c0, int c1, int c2,int c3,int c4)
There is no code associated with this signal.

16. Next we need a C++ class that implements arithmetic of finite fields.  Objects of this class can be added, subtracted, multiplied, and divided.  The class has no user interface, and you will be able to reuse it in the next project.
Choose Project...New Class... from the menu.
The Classname is GFElement, and there is no Baseclass.
Add these member variables:
bool valid;
int prime;
int power;
int c[9];
The last of these holds the five coefficients of the polynomial in order of increasing exponent.
It has enough space so that you can multiply fourth-degree polynomials.

17. Add this member function to initialize an element:
void GFElement::init(int pr, int pow){
  valid = true;
  prime = pr;
  power = pow;
}

Add this member function to set the coefficients in the polynomial for an element:
void GFElement::setValue(int c0 = 0, int c1 = 0, int c2 = 0, int c3 = 0, int c4 = 0){
  c[0] = c0;
  c[1] = c1;
  c[2] = c2;
  c[3] = c3;
  c[4] = c4;
  c[5] = c[6] = c[7] = c[8] = 0;
}

Add this member function to reduce all coefficients to the range {0, ..., prime -1}
Later, you will have to add the code to reduce exponents that exceed power.
void GFElement::reduce(){
//TODO -- get rid of nonzero coefficients whose index is power or higher
//by using an appropriate irreducible polynomial
   for (int i = 0; i < power; i++) {
     while (c[i] < 0)
        c[i] += prime;  //avoid negative numbers
     c[i] = c[i] % prime;
   }
}

18. Add these member functions to do addition, subtraction, and multiplication.
The last of them will need substantial enhancements when power is > 1.
GFElement GFElement::operator+(GFElement e){
  GFElement sum  = *this;
  for (int i = 0; i < 9; i++)
     sum.c[i] += e.c[i];
  reduce();
  return sum;
}

GFElement GFElement::operator-(GFElement e){
  GFElement sum = *this;
  for (int i = 0; i < 9; i++)
     sum.c[i]  -= e.c[i];
  reduce();
  return sum;
}

GFElement GFElement::operator*(GFElement e){
  GFElement product = *this;
  if (power == 1)
     product.c[0]  *= e.c[0];
//TODO - deal with higher values of power
  reduce();
  return product;
}

19. Add these functions for division.
The function inverse(), which simply tries every element of the field until it finds the inverse, will need more code to deal with the case power > 1.
GFElement GFElement::inverse(){
  reduce();
  GFElement result = *this;
  GFElement invalid = *this;
  invalid.valid = false;
//Check that it's not zero
  bool nonzero = false;
  for (int i = 0; i < 5; i++)
     nonzero |= (c[i] > 0);
  if (!nonzero) {
    return invalid;
  }
  GFElement unity = *this;
  unity.setValue(1);
  if (power == 1) {
    for (int i = 0; i < prime; i++) {
      if ((*this * result) == unity)
          return result;
    }
  }
//TODO -- deal with larger values of power
  return invalid;  // to keep the compiler happy
}

bool GFElement::operator==(GFElement e){
  reduce();
  e.reduce();
  for (int i = 0; i < power; i++)
     if (c[i] != e.c[i])
        return false;
  return true;
}

GFElement GFElement::operator/(GFElement e){
  return (*this * e.inverse());
}

20. Finally, add this function to create a representation of the polynomial that can be displayed as rich text.
QString GFElement::asText(){
  reduce();
    QString text = "[";
  if (c[4] > 1)
     text += QString("%1").arg(c[4]);
  if (c[4] > 0)
     text += "x<x>4</x>+";
  if (c[3]> 1)
     text += QString("%1").arg(c[3]);
  if (c[3]> 0)
     text += "x<x>3</x>+";
  if (c[2] > 1)
     text += QString("%1").arg(c[2]);
  if (c[2] > 0)
     text += "x<x>2</x>+";
  if (c[1] > 1)
     text += QString("%1").arg(c[1]);
  if (c[1] > 0)
     text += "x+";
  if(text == "["  || (c[0] > 0))
       text +=  QString("%1").arg(c[0]);
  text.stripWhiteSpace();
  if (text.right(1) == "+")
       text = text.left(text.length()-1);
  return text+"]";
}
At the top of gfelement.h
#include <qstring.h>

21. Open up gfbase.ui in Qt Designer and add the following widgets across the bottom.
At the left, a TextLabel about 100 x 30 pixels (icon has big letter A) with name TextOperand1, no text (the empty string), frame Shape Box, frame Shadow Sunken.
In the middle, a TextLabel about 100 x 30 pixels (icon has big letter A) with name TextOperand2, no text, frame Shape Box, frame Shadow Sunken.
At the left, a TextLabel about 100 x 30 pixels (icon has big letter A) with name TextResult, no text, frame Shape Box, frame Shadow Sunken.
Between the two operands, a ButtonGroup (icon just to the right of Group Box) with name ButtonGroupOp and title Operation.
Inside this, four small Push Buttons
name PushButtonAdd, text +, buttonGroupId 0
name PushButtonSubtract, text -, buttonGroupId 1
name PushButtonMultiply, text *, buttonGroupId 2
name PushButtonDivide, text /, buttonGroupId 3
Be sure the button GroupId is correct for the above buttons!
Between the second operand and the result, one small Push Button
name PushButtonEquals, text =.

22. Use Edit..Slots to add four slots:
slotButton(int, int, int, int, int)
slotNewPage(QWidget*)
slotOpButton(int)
slotEquals()
Then make the following connections by pressing F3 and dragging from the object that emits the signal to empty space on the main widget.
For PushButtonEquals, connect clicked() to slotEquals()
For ButtonGroupOp, connect clicked(int) to slotOpButton(int).  (Click inside the button group, but not on a button)
For TabWidgetMain, connect currentChanged(QWidget*) to slotNewPage(QWidget*)
For each of the three buttons on the Order 3 tab and for the one button on the Order 27 tab,
connect clicked(int, int, int, int, int) to slotButton(int, int, int, int, int)
Close Qt Designer.

23. Add the following member variables to the GF class
GFElement leftOp;
GFElement rightOp;
GFElement result;
int operation;
stateEnum state;

At the top of gf.h, add
#include "gfelement.h"
enum stateEnum {STATE_LEFT, STATE_OP, STATE_RIGHT};
Since the Order 3 tab will be displayed when the application starts, add appropriate initialization at the end of the GF constructor:
   leftOp.init(3,1);
  rightOp.init(3,1);
 
 

24. Now, in the GF class, override the following slot functions that you added to GFBase.

When the user selects a new page on the tab widget, reinitialize all the field elements
void GF::slotNewPage(QWidget* w){
  QString label =  TabWidgetMain->tabLabel(w);
  int power;
  int prime;
  if (label == "Order 3") {
    power = 1;
    prime = 3;
  }
  else if (label == "Order 27") {
    power = 3;
    prime = 3;
  }
  else if (label == "Order 5") {
    power = 1;
    prime = 5;
  }
//TODO -- add values of prime and power for other tabs
  leftOp.init(prime, power);
  rightOp.init(prime, power);
  TextOperand1->setText("");
  TextOperand2->setText("");
  TextResult->setText("");
  state = STATE_LEFT;
}

When a button on one of the tabs is pressed, fill in the appropriate operand
void GF::slotButton(int c0, int c1, int c2, int c3, int c4){
  switch(state) {
    case STATE_LEFT:
      TextOperand2->setText("");
      TextResult->setText("");
//fall through
    case STATE_OP:
      leftOp.setValue(c0, c1, c2, c3, c4);
      TextOperand1->setText(leftOp.asText());
      state = STATE_OP;
      break;
    case STATE_RIGHT:
     rightOp.setValue(c0, c1, c2, c3, c4);
     TextOperand2->setText(rightOp.asText());
     break;
   }
}

When an arithmetic button is pressed, record the desired operation
void GF::slotOpButton(int ID){
  operation = ID;
  state = STATE_RIGHT;
}

When the equals button is pressed, do the arithmetic and display the result
void GF::slotEquals(){
  switch (operation) {
    case 0:
         result = leftOp+ rightOp;
         break;
    case 1:
         result = leftOp- rightOp;
         break;
    case 2:
         result = leftOp* rightOp;
         break;
    case 3:
         result = leftOp/ rightOp;
         break;
    }
    TextResult->setText(result.asText());
    state = STATE_LEFT;
}

25. Build and run the project.  Everything should work fine for Order 3. When you switch to Order 27, you should be able to push the one button, see the left operand displayed correctly, and add it to itself.

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 tab widget page of the size that we have used), some
interesting possibilities are
4, 9, 25, 49 for power = 2
8, 27  for power = 3
16 for power = 4
32 for power = 5.
When power is greater than 1, you need to "simplify" the result of polynomial multiplication by taking the result modulo an irreducible
polynomial. That will require enhancements to GFElement::reduce().
Here are some good choices for irreducible polynomials. 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 prime = 2
power = 2:   x2 + x + 1 = 0    so replace x2 by -x -1(which is the same as x + 1)
power = 3:   x3 + x + 1 = 0    so replace x3 by -x -1(which is the same as x + 1)
power = 4:   x4 + x + 1 = 0    so replace x4 by -x -1(which is the same as x + 1)
power = 5:   x5 + x2 + 1 = 0    so replace x5 by -x2 -1(which is the same as x2 + 1)

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

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

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

26. To transfer your project to another computer, or to hand it in, first choose Build..DistClean from the main menu (not essential, but it saves
space, so that even a large project fits on a floppy).  Then choose Tools.Ark.  Either choose File...New from the menu or click the leftmost
(New) icon on the toolbar.  Navigate to the directory just above proj_gf (so that you see the folder proj_gf in the window), and type in
proj_gf.zip as the file name.  (For handing in homework, you may also need to build your own name into the file name -- see instructions).
Click Save.  Now choose Action...Add Directory (or click the fourth icon from the left on the toolbar).  Double-click on the directory
proj_gf to move to it. You will see four subdirectories, including gf.  Click OK.  You should see all the files in the archive, but sometimes Ark
will say "No files in current archive."  Don't worry-- just exit.  Choose Tools...Ark, then choose File...Open and navigate to the directory
above proj_gf, and double.click on proj_gf.zip.  You should see a directory tree whose root is proj_gf.

27. To install the project to another computer, save proj_gf.zip on a floppy.  On the new computer, start up KDevelop and choose Tools...Ark.  Open proj_gf.zip on the floppy. Navigate to the directory above where you want proj_gf to be, and choose Action...Extract (or click the Extract icon on the toolbar).  You should then be able to open and build the project.

28. If the project fails to build correctly on the other computer (perhaps because it has a different version of Qt or KDE), follow the instructions in the file Kexamples.html -- build an empty KDE project in a different directory and add all the source files to it.
 

Grading standards:
Getting GF[3] to work (just following the instructions) 5 points
Also getting GF[5] and GF[7]  to work (power = 1) : 6 points
Also getting GF[4]  to work (power = 2, but you can hard-code each case) : 7 points
Also GF[9]  to work (power = 2)  : 8 points
For the next two the polynomial multiplication starts to get hard
Also getting GF[8]  to work (power = 3)  : 9 points
Also getting GF[16] (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](prime = 5)  to work : 11 points
Also getting GF[27](prime = 3, power = 3)  to work :12 points
Also getting GF[49](prime = 7)  to work : 13 points
Also getting GF[32](power = 5)  to work : 14 points
(There will be a limit of 40 points for all 4 programming exercises in the course, however)