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)