Feeds:
Posts

## Elliptic Curve Cryptography and Finite Fields

Back around 2000, I found a copy of Neal Koblitz’s text A Course in Number Theory and Cryptography at the Borders bookstore in Bangor, Maine.  I only worked my way through the first chapter, but was fascinated with these ideas.  I found Professor Koblitz’s website which, at the time, had a tutorial section on finite fields and elliptic curve cryptography (this may have been on the Certicom website, I can’t remember now).  I moved on to other forms of digital cryptography, like the Diffie-Hellman Key Exchange and RSA Cryptosystem, but always appreciated Prof. Koblitz’s work.  Recently, we dressed up for Halloween as a number and I chose to be the number 4.  As part of my costume, I drew the addition table for the Galois Field of order 4$GF(4)=^{GF(2)[x]}/_{x^2+x+1}$, and did a lot of thinking that week about the element a, which was defined as the root of the equation $0=x^2+x+1$ in $GF(2)$

This past week, I decided to look at the mathematics behind Bitcoin and blockchain, and lo and behold, it is Finite Fields and Elliptic Curve Cryptography – I don’t know why it took me so long to find this out, but now I’m excited about these topics.  I am a little skeptical about the current “Bitcoin bubble.”  I’m not sure that these valuations are sustainable, but from everything I’ve read, the blockchain algorithm behind Bitcoin is revolutionary and the mathematics is “supercool.”

Here’s a graph of the equation $y=x+1$ in $GF(2)$.

## On the Importance of Algebra

About fifteen years ago, when the WorldWideWeb was still text-based, I came across some of the writings of Professor Richard Mitchell (1929-2002).  Mitchell was a Professor of English and Classics at Glassboro State College in New Jersey, now known as Rowan University.  Although he was a specialist in grammar, literature and the humanities in general, he had a tremendous appreciation for mathematics and a deep and penetrating understanding of what constitutes mathematics and what it’s good for.  These short excerpts below come from his two essays, “The Uses of Audacity” and “Wise Choices in Peoria.”

From “The Uses of Audacity”

Algebra is a world of principle, and a dramatic revelation of the power of principle. In fact, algebra, and even algebra alone, could provide a true and sufficient education out of which to understand the worth of living by principle…

…[Y]ou will have it in your mind that you can know something–truly know it, and not just believe it, or be informed of it–and maybe, since that is so, you can truly know something else. It’s interesting to wonder what such a something else might be.

…You will find that algebra shows you some truths. The first great truth is that there can be something real, and complete, and harmonious, and even, in some strange way, absolutely perfect right in your own mind, and made by you alone. You will see that you have a wonderful freedom not mentioned in the Bill of Rights, the freedom to decide what your mind will contain and how it will work.  You don’t have to copy the rest of the world.

Algebra tells sad truths too. Where there is no balance, there is no truth. What is equal is equal, and between the equal and the unequal there is no conference table, no convenient compromise. In this terrible law there is a hinting question for all of life…

Algebra will show you the inexorable, the endless and permanent chain of consequence, the dark thread of necessity that brought you to a wrong answer because of a tiny little mistake back in the second line. I know how unfair that seems, and how scary that what seems unfair is nevertheless justice. Is life like that too, as all of nature seems to be? How then shall we live? What are the laws of the algebra of our living, and where do they exist, where created? Who can show us how to learn them?

It takes some serious living to see the truth hidden in algebra…

From “Wise Choices in Peoria”

[Some people]…assume that things like geometry and the multiplication table are taught in schools only out of tradition, and they are easily seduced into believing that such arts are useless to those who aren’t going to make some money from them.

But in fact the mathematical arts are the best studies in which to learn certain truths that are essential to the making of wise choices. It is in mathematics that we most readily see that the permanent relationship between principle and necessity is not subject to appeal, that every particular is a local manifestation of some universal, that there is a demonstrable difference between what we believe and what we know, and that experience can never do the work of logic. It is in mathematical studies that a child … can have his first inkling of Justice and Truth…

## Derivation of the Cross Product

A few weeks ago, my colleague who teaches Physics asked me about the derivation and justification of the cross-product formula.

The cross product for two vectors will find a third vector that is perpendicular to the original two vectors given.

The given vectors are assumed to be perpendicular (orthogonal) to the vector that will result from the cross product.  This means that the dot product of each of the original vectors with the new vector will be zero.

So, given two vectors $a=\begin{bmatrix} a_1\\ a_2\\ a_3 \end{bmatrix}$

and $b=\begin{bmatrix} b_1\\ b_2\\ b_3 \end{bmatrix}$

we want to find a third vector $n=\begin{bmatrix} n_1\\ n_2\\ n_3 \end{bmatrix}$

so that $n$ is perpendicular to both $a$ and $b$

As I mentioned above this means that we want the dot product of $n$ with each of the two original vectors to be zero.

$a \cdot n=a_1n_1+a_2n_2+a_3n_3=0$

and

$b \cdot n=b_1n_1+b_2n_2+b_3n_3=0$

This gives us two equations to work with.  Since we have three variables to solve for $(n_1, n_2, n_3)$, we’ll need another equation to work with.

The website Heaven’s in the backyard introduces a third constraint that the modulus of the cross product vector $n$ be equal to 1.

This creates a third equation $n_1^2+n_2^2+n_3^2=1$ and allows us to solve for $n_1, n_2,$ and $n_3$ in terms of $a_1, a_2, a_3, b_1, b_2$ and $b_3$

As mentioned above the web page Heaven’s in the backyard does a nice job with the derivation of the values for $n_1, n_2,$ and $n_3$ and ends up with the formula $n=\begin{bmatrix} a_2b_3-a_3b_2\\ a_3b_1-a_1b_3\\ a_1b_2-a_2b_1 \end{bmatrix}$.

I don’t see this mentioned in the derivation, but it appears that the $\sqrt{Z}$ term that is factored out and defined to make the derivation work more smoothly is actually the modulus of the cross product vector $n$.

Assuming that the cross product vector has a length of $1$ results in an answer that is multiplied by $\frac{1}{\sqrt{Z}}$, because the actual perpendicular $(n)$ has a modulus equal to $\sqrt{(a_2b_3-a_3b_2)^2+(a_3b_1-a_1b_3)^2+(a_1b_2-a_2b_1)^2}$ which is $\sqrt{Z}$.

After working through some of these ideas, I became interested in where the cross-product came from.

At Wikipedia, they mention that Joseph-Louis Lagrange, the French/Italian mathematician of the late 18th century provided a formula for this in a paper from 1773 that was focused on the properties of a tetrahedron.  The calculations related to the cross-product appear in the first few pages of the paper.  Lagrange posits 9 “quantités” $x, y, z, x', y', z', x'', y'', z''$ and then proceeds through a blizzard of calculations based on these quantities.

If each triplet of values $q=(x, y, z)$, $r=(x', y', z')$ and $s=(x'', y'', z'')$ is considered as the coordinates of a vector, then the first calculations are the cross-products of each vector with each of the others.  In Lagrange’s notation, we could identify each of the cross products as

$r \times s=\begin{bmatrix} \xi\\ \eta\\ \zeta \end{bmatrix}$, $q \times s=\begin{bmatrix} \xi'\\ \eta'\\ \zeta' \end{bmatrix}$, $q \times r=\begin{bmatrix} \xi''\\ \eta''\\ \zeta'' \end{bmatrix}$

On the following page Lagrange identifies the square of the modulus for each of the cross-product vectors as $\alpha$, $\alpha'$ and $\alpha''$

Several pages later Lagrange notes that the dot product of each original vector with the appropriate cross-product produces a zero result.

There are two things that fascinate me about this – (1) the depth of this seemingly simple question – how do you justify the cross-product formula? and (2) what was Lagrange up to in this paper? – what is the purpose of the multitude of calculations that he completes in the paper from 1773 (Solutions analytiques de quelques problèmes sur les pyramides triangulaires)?

## Synthetic Division (again)

One of my colleagues recently found an interesting paper that generalizes the synthetic division algorithm so that it can be used for any polynomial division problem.

## Synthetic Division

We just finished talking about synthetic division in the College Algebra course today and got into a discussion of how to represent the remainder.  For example, given the problem:

$\frac{x^4-2x^3-x+10}{x-2}$

The answer turns out to be: $x^3-1 R: 8$ or you can say that the answer is: $x^3-1+\frac{8}{x-2}$.  This all goes back to the division algorithm which says that given two numbers $a$ and $b$, then solving the problem $\frac{a}{b}$ means finding $q$, the quotient and $r$, the remainder such that $a=b*q+r$ (with $r) .

If we take the expression $a=b*q+r$ and divide on both sides by $b$, then we’ll have $\frac{a}{b}=\frac{b*q}{b}+\frac{r}{b}$ or $\frac{a}{b}=q+\frac{r}{b}$.

Which of these forms we prefer depends on whether we want to say that:

$x^4-2x^3-x+10=(x-2)(x^3-1)+8$

or

$\frac{x^4-2x^3-x+10}{x-2}=x^3-1+\frac{8}{x-2}$

## In Defense of Algebra

The American Mathematical Association of Two-Year Colleges (AMATYC) is in the process of putting together a position statement on the Appropriate Use of Intermediate Algebra as a Prerequisite Course that will annul the requirement that students pursuing a four-year degree in disciplines other than the hard sciences take and pass a course in Intermediate Algebra.  While this won’t directly impact students who initially enroll at four-year schools, it will have an enormous impact on math education at the nation’s community and technical colleges.  Some schools may amend their Intermediate Algebra courses without destroying the core topics, but I fear that others will end up going down the same road that many high schools did during the rush to get rid of algebra at the K-12 level during the 1990s.

The “reform math” movement of the 1990s led to a plethora of poorly written NSF-backed “math” textbooks such as Core-Plus and IMP at the high school level and MathLand and Everyday Math at the elementary level.  The repercussions of this misguided effort to reform math education at the K-12 level are still felt today, and in some places the fight continues.  The Seattle School Board was taken to court in 2009-10 over its mathematics textbook selection process and a King County Superior Court judge ruled their selection of the Key Curriculum “Discovery” series to be arbitrary and capricious.  An appeals court in 2011 reversed that decision and the textbook selection was allowed to stand.

The upshot of the use of reform materials at the K-12 level is that developmental math enrollment at the two and four-year colleges and universities has exploded.  The solution – stop teaching algebra there as well.

I respectfully disagree.  Here is the text of an email I’ve sent to AMATYC regarding their position statement:

I am responding to the AMATYC position statement on the Appropriate Use of Intermediate Algebra as a Prerequisite Course.  I have also copied Jerry Kissick, the President of ORMATYC, on this email as I believe that ORMATYC should adopt a position statement on the importance of Beginning and Intermediate Algebra to a Liberal Arts education.

I have been a Mathematics Instructor at Clatsop Community College in Astoria, Oregon for 10 years and taught high school mathematics for 6 years prior to entering the MA program in Mathematics at the University of Maine in the fall of 2000.  It is my professional opinion that Beginning and Intermediate Algebra are appropriate prerequisites for college level mathematics no matter the area of specialization of the student.

Any student expecting to receive a four year degree should have demonstrated an understanding of Beginning and Intermediate Algebra at some point in their academic career.  Students who are enrolled in vocational degree or certificate programs at two-year colleges should have different requirements based on their program of study.

Most four-year colleges and universities require that their students demonstrate an understanding of Beginning and Intermediate Algebra prior to matriculation at the college or university.  This is normally done through the submission of SAT or ACT scores after the completion of high school algebra courses.  At two-year colleges, developmental mathematics courses offer an opportunity for students to demonstrate understanding of Beginning and Intermediate Algebra, after which they may then transfer to a four-year school.

Algebra is one of the foundations of a Liberal Arts education and, together with arithmetic, form the conceptual foundation for all of mathematics.  Algebra is a prerequisite to Statistics.  Statistics is not a separate discipline wholly apart from the rest of mathematics – a true understanding of statistics requires an understanding of Beginning and Intermediate Algebra.

Civil rights activist Bob Moses has spent the past 25 years running the Algebra Project, trying to help minority students achieve a better understanding of algebra because he believes that access to quality algebra instruction is a civil rights issue.  Here is a link to an NPR story on Bob Moses.

The importance of Algebra to a student’s overall education demands that we not abdicate our responsibility to teach the subject, but rather work to ensure that we do a better job teaching the subject to all students.

The reform of California’s K-12 mathematics standards in the 1990s led an explosion of developmental enrollment in the California CC and Cal State systems.  This was not related to the topics in the Beginning and Intermediate Algebra curriculum, but rather to the preparation (or lack thereof) the students received at the K-12 level.  The Complete College America organization has recently been an active proponent of “alternative math pathways.”  I find it telling that the organization is called “Complete College America,” rather than “Educate American Students.”  Their focus appears to be getting students to a diploma without the academic and intellectual underpinnings that a college diploma normally represents.

I do often see students struggling to make sense of the work in their mathematics courses.  However, I also see them mature both emotionally and academically as a result of those struggles.  This is the purpose of education – to help our students to mature intellectually as a result of their engagement with the course material.

Algebra as a discipline has a history that goes several millennia deep in human culture.  The works of Diophantus, Brahmagupta and Al-Khwarizmi are beautiful, ineluctable parts of human heritage, and this is not to mention the more “recent” work of Fibonacci, Cardano, Fermat and Des Cartes.  While their techniques and notation may be archaic, it is the power of their reasoning that shines through across the centuries.

A liberal arts education is not and should not be a form of job training.  Many of my students will not directly use much mathematics in their chosen profession and they know this.  However, they are still interested in being an educated person, which means having the background in a broad range of human knowledge so as to be able to think independently about the world and society in which they live.

Thank you for your consideration of my opinion regarding the AMATYC position statement on the Appropriate Use of Intermediate Algebra as a Prerequisite Course.  I have also attached a series of essays written by individuals who believe as I do that Beginning and Intermediate Algebra are part of the foundation of a Liberal Arts education.

Sincerely,

Richard W. Beveridge

Mathematics Instructor

Clatsop Community College

The links for the attachments I mention in the letter are below:

Daniel Willingham at the Washington Post’s Answer Sheet blog

Jessica Lahey at the New York Times’ Motherlode blog

Nicholas Warner at the Huffington Post

Evelyn Lamb at Scientific American’s Observations blog

Jennifer Ouellette at Scientific American’s Cocktail Party Physics blog

## The Farmer and the Fencing

Four years ago I wrote a post about math education that mentioned the problem of “The Farmer and the Fencing.”  The link for the post is here and a sample assignment from an Elementary Algebra (Algebra I) course is here.  I mentioned in that post that I’ve used this problem at a variety of levels of mathematics starting with the 7th grade.

For the 7th grade class, we looked at some possible values for the length and width of the pen that was to be constructed from the fencing and made a table of values showing the length, width and area of the pen for each set of values.

The project from the Elementary Algebra class that is linked above addresses the question from a somewhat more sophisticated level, asking the students to introduce variables for the length and width and then substitute in for one of the variables to arrive at an expression for the area as a function of only one of the dimensions.  The students can then find the maximum area using a graphing calculator.

In a Pre-Calculus class I taught during the 1999-2000 school year, we covered a unit that considered the parabola as a conic section and included applications on projectile motion and maximum and minimum values.  In the Pre-Calculus class, we found the max or min by finding the vertex of the parabola defined at the point $x=\frac{-b}{2a}$ and $y=f(\frac{-b}{2a})$.  We didn’t need Calculus to determine this, the $\frac{-b}{2a}$ can be defined from the vertex form of the equation of a parabola $y=n(x-h)^2+k$.  With a little classical algebra, you can show that $h=\frac{-b}{2a}$.

If you expand $y=n(x-h)^2+k$

$y=n(x^2-2hx+h^2)+k$

$y=nx^2-2nhx+nh^2+k$

Then

$\frac{-b}{2a}=\frac{2nh}{2n}=h$

I taught Differential Calculus as a grad student at the University of Maine in 2003 and we covered The Farmer and the Fencing from the perspective of Calculus, in which we differentiate the area equation and set the derivative equal to zero to find the maximum area.  The problems can be spruced up a little by dividing the pen into smaller pens using cross-sectional pieces.

In the fundamental problem the maximum area of a simple pen with four sides and no cross-divisions is arrived at by splitting the perimeter equally among the four sides to make a square.  If the pen is cross divided in any way, the maximum area comes from a scenario in which half of the perimeter is allocated to the lengthwise pieces and the other half allocated to the any widths.

If there are $m$ lengths and $n$ widths then the perimeter is represented by $ml+nw=P$.  The area is $A=l*w$.  If we isolate the length in the perimeter equation and substitute it into the area equation, we can then differentiate the area equation for an answer for the general problem of maximum area of a pen with $m$by $n$ crosspieces:

$ml+nw=P$

$ml=P-nw$

$l=\frac{P-nw}{m}$

$l=\frac{P}{m}-\frac{nw}{m}$

Then substituting into the area equation:

$A=l*w$

$A=(\frac{P}{m}-\frac{nw}{m})*w=\frac{P}{m}*w-\frac{n}{m}*w^2$

So, the area equation is then

$A=\frac{P}{m}*w-\frac{n}{m}*w^2$

Which makes the derivative

$A'=\frac{P}{m}-\frac{2n}{m}*w$.

Setting this equal to zero and solving for $w$:

$0=\frac{P}{m}-\frac{2n}{m}*w$

$\frac{P}{m}=\frac{2n}{m}*w$

$\frac{m}{2n}*\frac{P}{m}=w$

$\frac{P}{2n}=w$

or

$\frac{P}{2}=nw$

which means that half of the perimeter should be allocated to the $n$ widths and the other half to the $m$ lengths.

For example, if the farmer has 300 feet of fencing, the maximum area is a square that is 75 feet on each side.

If the pen is split into two smaller pens with a crosswise fence, then the maximum area will allocate 150 feet to the widths (75 feet each) and 150 feet to the three lengths (50 feet each).

When I taught this problem in 1999-2000 I asked myself what might happen if the pen were to be divided on the diagonal creating two triangular pens.  Little did I know how much this would complicate such a simple little problem.

The Briggs and Cochran Calculus textbook includes a similar problem in its section on optimization (problem 10c on pg. 214).  In a key modification that makes the problem solvable for Calculus I students, they eliminate one of the lengths of the figure by placing the pen against a barn.

This eliminates one of the lengths in the problem.  Let’s look at the solution to this problem before we tackle the more general version which requires that both lengths come from the available fencing.  In the problem in the textbook, 200 meters of fencing are to be used, so the constraint on the amount of fencing creates the following equation:

$l+2w+\sqrt{l^2+w^2}=200$

If we want to maximize the area of the pen then we need to substitute for one of the variables and find the derivative of the area equation:

$l*w=A$

In order to substitute we need to isolate one of the variables from the constraint equation.  This will involve getting the square root by itself so that we can square both sides of the equation:

$l+2w+\sqrt{l^2+w^2}=200$

$\sqrt{l^2+w^2}=200-2w-l$

$(\sqrt{l^2+w^2})^2=(200-2w-l)^2$

$l^2+w^2=(200-2w-l)(200-2w-l)$

$l^2+w^2=40,000-400w-200l-400w+4w^2+2lw-200l+2lw+l^2$

$l^2+w^2=40,000-800w-400l+4w^2+4lw+l^2$

This is where this problem differs from the general problem, in that the two $l^2$ terms cancel each other out and allow us to isolate the $l$

$w^2=40,000-800w-400l+4w^2+4lw$

We’ll move both terms that contain the $l$ to the same side, so that we can factor out $l$ and then divide through by $400-4w$

$400l-4lw=40,000-800w+3w^2$

$l(400-4w)=40,000-800w+3w^2$

$l=\frac{40,000-800w+3w^2}{(400-4w)}$

So now our area equation becomes:

$\frac{40,000-800w+3w^2}{(400-4w)}*w=A$

OR

$\frac{40,000w-800w^2+3w^3}{(400-4w)}=A$

Finding the derivative for this is pretty messy and strains the display capabilities of this blog!  We’ll do our best to show the work here:

$\frac{(400-4w)(40,000-1600w+9w^2)}{}$

$\frac{-(40,000w-800w^2+3w^3)(-4)}{16(100-w)^2}=A'$

$\frac{(16,000,000-640,000w+3600w^2-160,000w+6400w^2-36w^3)}{}$

$\frac{+160,000w-3200w^2+12w^3)}{16(100-w)^2}=A'$

So, combining like terms:

$-640,000w-160,000w+160,000w=-640,000w$

$3600w^2+6400w^2-3200w^2=+6800w^2$

$-36w^3+12w^3=-24w^3$

$\frac{(16,000,000-640,000w+6800w^2-24w^3)}{16(100-w)^2}$

And then cancel a common factor of 8 in the numerator and denominator:

$\frac{(2,000,000-80,000w+850w^2-3w^3)}{2(100-w)^2}$

The simplified expression for the derivative is:

$\frac{-3w^3+850w^2-80,000w+2,000,000}{2(100-w)^2}=A'$

So from this we need to set the numerator equal to zero.  In the textbook, there is no indication that technology will be necessary to complete the problem, but I don’t see any way around using a graphical solution to finding the root of the derivative.  I suppose there is always the cubic formula, but that is truly an anachronism.  Here’s what the graph of the derivative looks like with the root indicated:

From the graph, we can conclude that:

$w\approx 38.814$

$l\approx 55.03$

and the crosspiece $\sqrt{l^2+w^2}\approx 67.34$

We’ll look at the diagonal problem without the barn (which leads to a Lagrangian solution) in another post.