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)$.

Recipe for a Leibniz Quarter Pi

Ingredient: $\frac{1}{1+x^2}$

Divide gently in a long division sauce pan:

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

Integrate briskly over a low flame:

$\int (1-x^2+x^4-x^6+x^8-x^{10}...)dx=$

$=x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+\frac{x^9}{9}-\frac{x^{11}}{11}+...$

Evaluate for $x=1$ and let stand at room temperature for 1000 terms for accuracy to three decimal places.

$=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\frac{1}{11}+\frac{1}{13}-\frac{1}{15}...$

But this doesn’t look like a pi! or taste like a pi!

or a quarter pi!

$\int \frac{1}{1+x^2}dx$

and make the trigonometric substitution $x=tan \theta$ so that $dx=sec^2 \theta d \theta$ then:

$\int \frac{1}{1+x^2}dx=\int \frac{1}{1+tan^2 \theta}sec^2 \theta d \theta$

and

$\int \frac{1}{1+tan^2 \theta}sec^2 \theta d \theta=\int \frac{1}{sec^2 \theta}sec^2 \theta d \theta$

$=\int d \theta=\theta$

which, if we return to the original substitution $x=tan \theta$, we see that $\tan^{-1} x=\theta$

So, $\int \frac{1}{1+x^2}dx=\tan^{-1}x$, which means that:

$\tan^{-1}x=x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+\frac{x^9}{9}-\frac{x^{11}}{11}+...$

and since $\tan^{-1}(1)=\frac{\pi}{4}$, then

$\frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\frac{1}{11}+\frac{1}{13}-\frac{1}{15}...$

The Many Solutions of the Population Equation

I never studied the logistic equation as a student.  I first encountered this relationship as an instructor in one of the College Algebra textbooks I was reviewing and/or teaching from and was intrigued by the application of this “growth with constraints” model to a natural resource.  In researching applying the logistic model to natural resource consumption, I immediately ran into M. King Hubbard’s work on Peak Oil.

Then, when I was teaching integral calculus last winter, we began a unit on separable differential equations.  I was poking around looking for good application problems that would utilize separable ODEs and ran into the fundamental population differential relationship $\frac{dP}{dt}=kP$, followed by the relationship I had used for the logistic $\frac{dP}{dt}=kP(1-\frac{P}{N})$ with $N$ defined as the “carrying capacity” or maximum growth for the population.

We went through the procedures for solving each of these ODEs (as well as the continuous mixing problems which follow a similar pattern) and then we moved on.

This year when I was teaching this topic again I was reminded of a paper my thesis advisor had given to me back in 2003 about the application of differential equations to modeling fish populations.  I was intrigued by the profusion of models that could be generated by changing the constraints for a given relationship.

Since I didn’t teach integral calculus for another 10 years after I read that paper, I had essentially forgotten most of the equations, formulas and relationships that generated the graphs that had stuck with me.  This year, while covering the separable ODEs with their applications, I began to look into the application of these relationships to fish populations and population in general.

I found two great resources that go through the set up of these relationships in a very clear manner, and each of them includes wonderful graphs showing the multiple solutions that result when the same differential relationship is solved with different initial conditions.

The opening section of Robert Borelli and Courtney Coleman’s Differential Equations: A Modeling Approach can be read here.

A student project from James Madison University written by Bailey Steinworth, Yuhui Wang and Xing Zhang can be read here.

Combinatorics

Yesterday in Pre-Calculus class we were discussing combinatorics and came across a series of questions on how many ways can a best 2 out of 3 sets tennis match be won and how many ways can a best 3 out of 5 tennis match be won.

For a 2 out of 3 scenario there are six possibilities (AA, ABA, BAA, BB, BAB, ABB) and for the 3 out of 5 scenario there are 20 possibilities (AAA, BAAA, ABAA, AABA, BBAAA, BABAA, BAABA, ABBAA, ABABA, AABBA and ten more in which B wins).

The question then came up of how to generalize these results.  The way I approached this was to consider how many ways one of the players could win and then double the answer to include the scenarios in which the other won.

One of the issues in this type of problem is that once the winner has won the required number of games the match ends, so that a best 2 out of 3 match could never end AAB, for instance.  Another issue is that each of the possibilities of winning in a different number of sets should be considered separately.  That is, winning in the minimum number of sets, then winning after having lost one set and so forth.

Taking all of these issues into account for a competition in which the winner must win $\frac{n+1}{2}$ out of $n$ leads to a general formula of $2*\displaystyle \sum_{k=0}^{\frac{n-1}{2}}{_\frac{n+2k-1}{2}}C_{k}$.

Or – if the winner must win $g$ out of $2g-1$ then the formula would be $2*\displaystyle \sum_{k=0}^{g-1}{_{g+k-1}}C_{k}$.

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)?

Income Inequality

Back in May of 2013, I did a presentation on income inequality that focused on how the Gini index is calculated.

Recently, I came across a graph that shows how the income growth during economic expansions has been distributed over the last 60 years.

It’s seems clear to me that the change in income tax rates during the Reagan years had a radical effect on income distribution in the US.

In his latest blog post, Robert Reich has a good analysis of some of the other issues that have led to the level of inequality we experience today.

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.