Mathematics 152
Project 2
A PHP Program for Finite Field Calculations
Last Modified: September 7, 2004
The initial design of this
project was done by Carli Collins and Zoltan Feledy, Harvard Extension
School graduate
students.
This project assumes that you have experience at programming in some
language: C, C++, Basic, Java, Perl, JavaScript .... and that you
have done project 1. You will
learn more PHP and HTML as
you go.
I. Create the User Interface
1.
Open
HapEdit. From the toolbar, choose Folders, and click on the icon for
the
project in which you did the permutation program. I will refer to it as
M152Bamberg, but your version should include your own name.
2.
Right click on the window with the file icons, and
select New...PHP Page. Save
this page as C:\EasyPHP\www\M152Bamberg\
calculator.php.
3.
Change the title tag of your document to Field
calculator
by <Your Name>, for example
<title>
Finite Field Calculator by
Paul Bamberg</title>
4.
Inserting a form:
- Place the cursor just above the
closing </body> tag, and
Select Actions...Form...Insert Form from the
menu
- Name the form calculation,
set the action to calculator.php,
and leave the Method as Post. Click OK. The
effect of the action will be, when the user clicks a button, to submit
the data that has been entered back to this PHP file for processing.
5.
Creating the first table:
Here is a simple plan for laying out the form as two tables. The
first table will contain one tab for each order of field that you
choose to implement. The second table will allow the user to
select two field elements and an operation, then push an "equals"
button to get the answer.
a. Put your cursor between the form
tags, and select Actions...Table...Insert Table… from the menu. On the
General tab set Width to -1. On the
Frame tab set border to 0. Click OK.
b. Put your cursor between the <table></table>
tags, then select Actions ...Table...Insert Cells… from the menu. On
the
General tab set Width to -1. Select
the Cell tab and input 3 into # of cells and 1 into #
of lines. Select the Alignment tab and choose Center as the horizontal
alignment.
c. In cell 1 (top left), denoted
by a <td></td> tag,
insert a link tag by selecting Actions... Link...Create link. For Page,
select calculator.php from the dropdown list
and click OK. Under Advanced, enter tab as the class. Now edit
the link so that it reads
<a class = "tab" href =
"calculator.php?order=3">Order
3</a>.
The class will let you assign a style. The ?order=3 will
cause the value 3 to be assigned to the PHP variable $_GET['order'].
The "Order 3" will display as the text of the link. Confirm this
by pressing F9 to run the PHP script. If
asked about a URL association, choose http://localhost/M152Bamberg
(with your own name).
d. In cell 2, just copy the link that you created, but edit it to read
<a class = "tab" href =
"calculator.php?order=4">Order
4</a>.
e. In cell 3, just copy the link that you created, but edit it to read
<a class = "tab" href =
"calculator.php?order=5">Order 5</a>.
When you implement fields of higher order, you can just add more
similar cells with "tab" links to this table.
f. In the PHP section just below the opening <body> tag, insert the line
$order =
isset($_GET['order'])?$_GET['order']:4;
This will assign a default value of 4 to $order when the script is first run,
so that you will never have an undefined variable.
7.
Creating the second table.
a. Put your cursor below the first table, and select
Actions...Table...Insert Table… from the menu. On the General tab set
Width
to 100%. On the
Frame tab set border to 0. Click OK. Select the entire table and choose
Actions...Text...Align text from the menu. Choose the alignment as
(Default), but enter tab-body as the class. Click OK. Under the line <div
class = "tab-body"> that was just created, use
Actions...Text...Insert paragraph, and edit the paragraph to read
<p>Order
<?php echo $order
?></p>
Confirm by pressing F9 that you can change the displayed order by
clicking on the tabs.
b.
Put your cursor between the <table></table>
tags, then select Actions...Table...Insert Cells… from the menu. On the
General tab set Width to -1. Select
the Cell tab and input 4 into # of cells and 2
into #
of lines. Select the Alignment tab and choose (Default)
horizontal
alignment. Click OK to create the cells.
c. The first cell in the first row will contain a dropdown list of all
the field elements. Place the cursor in the position for this
cell and choose Actions...Form...Insert options list from the menu.
Choose log1 as the name. For the options, type in 0, 1, x, and
x+1. These are just placeholders, correct for the default order
of 4.
d. The second cell in the first row will contain a dropdown list of all
the operations. Place the cursor in the position for this cell
and
choose Actions...Form...Insert options list from the menu. Choose oper
as the name. For the options, type in +, -, *, and /.
e. The third cell in the first row will contain another dropdown list
of all
the field elements. Place the cursor in the position for this
cell and
choose Actions...Form...Insert options list from the menu. Choose log2
as the name. For the options, again type in 0, 1, x, and x+1
f. The fourth cell in the first row will contain a button to do the
calculation. Place the cursor in the position for this cell and
choose Actions...Form...Insert button from the menu. Choose equals
as the name. Check "Provide value" and enter " = " (without any quotes)
as the value. Click OK. Press F9 to check that everything looks
correct in this row.
8.
Creating the output row
The second row of the table will display the result of your
calculation. Of course, that depends on which finite field the user
selected, so PHP will have to generate the answer. Delete all the
cells. Put your cursor between the <tr></tr>
tags, then select Actions...Table...Insert Cells… from the menu. Under
Cell, choose 4 for Colspan, 1 for # of cells, 0 for # of rows.
Under Alignment, choose center for Horizontal and middle for vertical.
Click OK.
Eventually PHP will have to fill in this row, but you can check its
appearance with a placeholder. Edit this cell like this:
<td
align="center" colspan="4"
valign="middle">
<?php
echo "[x] * [x] =
[x+1]";
?>
</td>
Then press F9 to
check the appearance of the entire form.
9. Applying styles to the
form
Place your cursor between the <head></head>
tags, under the <meta> tags. Type in
<link rel="stylesheet"
href="math152.css">
Append the
following to math152.css.
The first section makes the cells in the first row look like tabs.
The second section makes a tab turn red when the mouse hovers over it.
The third section sets the background color and spacing for the second
table.
.tab:link,
.tab:visited {
color:
#191970;
text-decoration: none;
padding: 0px 7px;
border-width: 1px;
border-style: solid solid none
solid;
border-color: #191970;
margin:
0 1px;
}
.tab:hover {
color:
Red;
text-decoration: none;
}
.tab-body {
background: #DCDCDC;
border:
1px solid #191970;
padding: 10px 10px 10px 10px;
}
10. Press F9 to make sure that the form looks all
right. It will become more interesting once we have added items to the
dropdown lists.
II. Implement the
mathematics
11. Now it is time to start work on the mathematics. Because the finite
field class will be reused, we will put it into a separate file. Create
a new PHP page in HAPEdit named FiniteField.php, and edit it so that it
is just
<?php
?>
Also create a test file named testfield.php with the contents
<?php
include_once("FiniteField.php");
$field =
MakeField(4);
echo
$field->ConvertPoly(0),"<BR>";
echo
$field->ConvertPoly(1),"<BR>";
echo
$field->ConvertPoly(2),"<BR>";
echo
$field->ConvertPoly(3),"<BR>";
echo
$field->Add("x","1"),"<BR>";
echo
$field->Multiply("x+1","x"),"<BR>";
?>
Because PHP error messages display unreliably in an HTML form, it is a
good idea to use testfield.php to test any changes that you make to the
finite field class.
12. The strategy for finite fields is to do multiplication and division
by means of logarithms, addition and subtraction by means of arrays of
coefficients. This means that every element of the field has three
different representations.
a. A logarithm, an integer, used for multiplication and division.
b. An array of integers that represent the coefficients of
polynomial in order of increasing exponent, used for
addition and subtraction. (e.g. array(1,2,3) means 3x
2 + 2x
+
1)
c. A displayable string, no spaces in it, that represents the
polynomial in a form suitable for display.
An array of arrays of polynomials, supplied to the constructor,
converts the first representation to the second.
The function ConvertPoly, listed below, converts the first or second
representation to the third.
A PHP array, indexed by strings, converts the third representation to
the first. This is built by the constructor.
The function MakeField builds a field of any order. You will
later add to this, and you will have to provide the right array of
arrays. Here is how to do it.
a. For logarithm 0, the first element, specify the multiplicative
identity 1.
b. For logarithm 1, the second element, specify any "primitive element"
whose powers generate all elements. Usually this can be 2 or x, but for
order 7 you will need to find a different primitive element.
c. Now specify in order all the powers of the primitive element, but
stop before you reach the identity again.
d. The last element, which has no logarithm, is 0.
Here is a good start on FiniteField.php. Paste it in, then work
at
understanding the function convertPoly() and the constructor. Be
sure that you can reconstruct the arrays that are provided as the last
argument to the constructor in MakeField.
You can run and modify testfield.php to test other examples of
arithmetic. You might even try to implement the field of order 9,
using the irreducible polynomial x
2+2x+2 and the primitive
element x.
<?php
class
FiniteField {
var
$polynomials; //an array of arrays of coefficients
var $logTable =
array(); //an array of integers, indexed by polynomials
var
$characteristic; //the prime number
var
$expon;
//the degree of the irreducible polynomial
var
$nElements; //the
number of elements
var
$nLog;
//the number of nonzero elements
function convertPoly($ar)
{
//overloaded so we
can pass it either a logarithm or an array of coefficients
//Convert a
logarithm if that is what is provided
if (is_int($ar)) {
$ar = $this->polynomials[$ar];
}
$displayString = "";
//Work
backwards, from largest exponent to smallest.
for ($n = count($ar)-1; $n >= 0; $n--) {
//For
n=0, we may need to display a zero if there is nothing else
if ($n == 0 && ($displayString == "" || $ar[0] > 0)) {
$displayString .= $ar[0];
}
//For
n=1, we don't display an exponent, and we suppress a coefficient of 1
elseif ($n == 1 && $ar[1] > 0) {
if ($ar[1] > 1) {
$displayString .= $ar[$n];
}
$displayString .= "x +";
}
//For n
>1 we display a coefficient if > 1 and we create a superscript
exponent
elseif ($n > 1 && $ar[$n] > 0) {
if ($ar[$n] > 1) {
$displayString .= $ar[$n];
}
$displayString .= "x&sup$n;+";
}
}
//If we
generated a lonesome final plus sign, get rid of it
if (substr($displayString,-1) == "+")
$displayString = trim(substr($displayString,0,-1));
//Make
sure there is no leading or trailing space
return trim($displayString);
}
//Here is the
constructor, which fills
in the logarithm table
function
FiniteField($charac, $power, $poly) {
$this->characteristic = $charac;
$this->expon = $power;
$this->polynomials = $poly;
$this->nElements = pow($charac, $power);
$this->nLog = $this->nElements - 1;
for($c = 0; $c < $this->nElements; $c++) {
$this->logTable[$this->convertPoly($c)] = $c;
}
}
function Add($i,
$j) {
$p1 = $this->polynomials[$this->logTable[$i]];
$p2 = $this->polynomials[$this->logTable[$j]];
$p3 = array();
for($c=0; $c < $this->expon; $c++) {
// you
must insert code to do the modular addition of coefficients
}
return $this->convertPoly($p3);
}
function
Multiply($i, $j) {
if ($i=="0" || $j=="0")
return "0";
$log1 = $this->logTable[$i];
$log2 = $this->logTable[$j];
$logProduct = 0; // you must replace this with code to do the modular
addition of logarithms
return $this->convertPoly($logProduct);
}
}
//This
function creates a field of any
order that it knows about
function
MakeField($order) {
switch($order) {
case 2:
return new FiniteField(2,1,array(array(1),array(0)));
case 3:
return new FiniteField(3,1,array(array(1),array(2),array(0)));
case 4:
return new FiniteField(2,2,array(array(1,0),array(0,1),
array(1,1),array(0,0)));
case 5:
return new
FiniteField(5,1,array(array(1),array(2),array(4),array(3),array(0)));
default:
echo "Field of order $order does not exist or is not implemented";
}
}
?>
13. You should next implement and test Subtract and Divide
functions. This is slightly tricky because the PHP modulus
operator a%b gives a non-negative result, which is what you want, only
if a is non-negative and b is positive. The Divide function
should return "error" as the result of division by zero.
After everything is working for order 4, test order 5.
Then implement and test order 7, using 3 as a primitive element.
Next, implement and test order 9, using irreducible polynomial x
2+2x+2,
for which x is a primitive element.
Finally, implement and test order 8, using irreducible polynomial x
3+x+1,
for which x is a primitive element. To use x
2 in testing,
enter it as "xsup2;". In each case, you will have to work out the
powers of the primitive element by hand.
If you are going to stop at this point, make sure that your
testfield.php does a thorough job of testing orders 7, 8, and 9, with
examples of all four operations for each.
III. Connect the
mathematics with the HTML
13. At the start of your PHP code, insert a line to include your finite
field class, and then create a field of the appropriate order, so that
you have:
include_once("FiniteField.php");
$order = isset($_GET['order'])?$_GET['order']:4;
$field = MakeField($order);
14. Now we need to display the field elements and operations in
the dropdown lists. This is slightly tricky, because we need to
remember which item was selected when we redisplay the form.
Modify the first cell with a dropdown to look like this. This takes
advantage of the fact that a PHP string enclosed in single quotes may
include literal double quotes. Notice that while a polynomial is
displayed as an item in the dropdown, its logarithm is stored as a
value that will identify the item. However, this logarithm is
converted into a string, and we will have to convert back.
<td>
<select name="log1" size="1">
<?php
for ($i = 0; $i < $order; $i++){
if ($log1 == $i)
echo '<option selected value =
"',$i,'">',$field->convertPoly($i),'</option>';
else
echo '<option value =
"',$i,'">',$field->convertPoly($i),'</option>';
}
?>
</select>
</td>
For the second cell with a dropdown, you can use the same approach to
marking the selection by putting the operators into an array, but here
the displayed character works fine as the associated value.
<td>
<select name="oper" size="1">
<?php
$operators = array("+","-","*","/");
for ($i = 0; $i < 4; $i++){
if ($oper == $operators[$i])
echo '<option selected =
"selected">',$operators[$i],'</option>';
else
echo
"<option>",$operators[$i],"</option>";
}
?>
</select>
</td>
For the third cell with a dropdown, use the same approach as for the
first one.
14. At the start of your PHP
code, you need to save the values
that have been specified by the user in the dropdown into PHP
variables. Fortunately, every element in a form has its value
saved in the global array $_POST. The index is the name, and the
array element is the value. This value is always a string,
though, and we must remember to convert the logarithms back to integers.
Insert the following code to accomplish this. Once this has been
done, you should be able to press F9 and see the four elements of
the field of order 4 displayed in each dropdown list. When you press
the equals button, the selected values in the dropdowns should be
preserved. So now the php code outside the form is
<?
include_once("FiniteField.php");
$order = isset($_GET['order'])?$_GET['order']:4;
$field = MakeField($order);
$log1
= isset($_POST['log1'])?intval($_POST['log1']):1;
$log2 =
isset($_POST['log2'])?intval($_POST['log2']):1;
$oper =
isset($_POST['oper'])?$_POST['oper']:"*";
?>
15. The equals button already does almost the right thing, but
we need to make sure that the order that has been chosen gets
remembered when the form is re-displayed. Just change the opening line
of the form to
<form
action="calculator.php?order=<?php echo $order;?>"
name="calculation"
method="post">
Now, by clicking
a tab, you can change the field to order 3 or 5. and the dropdowns will
be filled with the appropriate values.
16. Finally, you need to display the result of the calculation. This
means that you must replace the placeholder line
echo "[x] * [x] =
[x+1]";
by
$op1 =
$field->convertPoly($log1);
$op2 = $field->convertPoly($log2);
echo " [" . $op1 . "] " . $oper .
" [" . $op2 . "] " . "= [";
switch ($oper) {
case
"+":
echo $field->Add($op1, $op2);
break;
case
"-":
echo $field->Subtract($op1, $op2);
break;
case
"*":
echo $field->Multiply($op1, $op2);
break;
case
"/":
echo $field->Divide($op1, $op2);
break;
default:
echo "";
}
echo "]";
At this point, your calculator should work perfectly for order
3,
4, and 5, and it will be easy to add tabs for other orders.
16. Further enhancements are up to you.
Here is the grading scheme:
Basic Web page (part I): 2 points
Mathematics for orders 3, 4, and 5 (part II, including subtract and
divide functions): 4 points
Mathematics for orders 7, 8, and/or 9: 1 point for any, 2 points
for all 3
Finishing the interactive calculator (part III): 2 points
And then, if you get carried away and would like some extra credit, try
the following.
Field of order 25: 1 point
Field of order 27: 1 point
Field of order 16: 1 point
Field of order 32: 1 point
Field of order 49: 1 point
If you want to do these, it may be worthwhile to
add a function to FiniteField.php that generates the array of arrays
that is needed to create a new finite field, given an irreducible
polynomial. The only operation that is needed is multiplication by x,
followed by use of the polynomial to replace any power of x that is too
large.
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: x
2 + x + 3 = 0 so
replace
x
2 by -x -3 (which is the same as 6x + 4)