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

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