Skip to content →

# Tag: cryptography

One of the trends of 2010 was the proliferation of StackExchange sites. I guess by now most of us visit MathOverflow along with the arXiv daily. But, there are plenty of other StackExchange sites around that may be of interest to the mathematics-community :

“Opening a StackExchange site is damn hard. First you have to find at least 60 people interested in the site. Then, when this limit is reached, a large amount of people (in the hundreds, but it really depends on the reputation of each participant) must commit and promise to create momentum for the site, adding questions and answers. When this amount is reached, the site is open and stays in closed beta for seven days. During this time, the committers have to enrich the site so that the public beta (which starts after the first seven days) gets enough hits and participants to show a self-sustained community.” (quote from ForTheScience’s StackExchange sites proliferation, this post also contains a list of StackExchange-projects in almost every corner of Life)

The site keeping you up to date with StackExchange proposals and their progress is area51. Perhaps, you want to commit to some of these proposals

or simply browse around area51 until you find the ideal community for you to belong to…

In ONAG, John Conway proves that the symmetric version of his recursive definition of addition and multiplcation on the surreal numbers make the class On of all Cantor’s ordinal numbers into an algebraically closed Field of characteristic two : On2 (pronounced ‘Onto’), and, in particular, he identifies a subfield
with the algebraic closure of the field of two elements. What makes all of this somewhat confusing is that Cantor had already defined a (badly behaving) addition, multiplication and exponentiation on ordinal numbers.

Over the last week I’ve been playing a bit with sage to prove a few exotic identities involving ordinal numbers. Here’s one of them ($\omega$ is the first infinite ordinal number, that is, $\omega={ 0,1,2,\ldots }$),

$~(\omega^{\omega^{13}})^{47} = \omega^{\omega^7} + 1$

answering a question in Hendrik Lenstra’s paper Nim multiplication.

However, it will take us a couple of posts before we get there. Let’s begin by trying to explain what brought this on. On september 24th 2008 there was a meeting, intended for a general public, called a la rencontre des dechiffeurs, celebrating the 50th birthday of the IHES.

One of the speakers was Alain Connes and the official title of his talk was “L’ange de la géométrie, le diable de l’algèbre et le corps à un élément” (the angel of geometry, the devil of algebra and the field with one element). Instead, he talked about a seemingly trivial problem : what is the algebraic closure of $\mathbb{F}_2$, the field with two elements? My only information about the actual content of the talk comes from the following YouTube-blurb

Alain argues that we do not have a satisfactory description of $\overline{\mathbb{F}}_2$, the algebraic closure of $\mathbb{F}_2$. Naturally, it is the union (or rather, limit) of all finite fields $\mathbb{F}_{2^n}$, but, there are too many non-canonical choices to make here.

Recall that $\mathbb{F}_{2^k}$ is a subfield of $\mathbb{F}_{2^l}$ if and only if $k$ is a divisor of $l$ and so we would have to take the direct limit over the integers with respect to the divisibility relation… Of course, we can replace this by an increasing sequence of a selection of cofinal fields such as

$\mathbb{F}_{2^{1!}} \subset \mathbb{F}_{2^{2!}} \subset \mathbb{F}_{2^{3!}} \subset \ldots$

But then, there are several such suitable sequences! Another ambiguity comes from the description of $\mathbb{F}_{2^n}$. Clearly it is of the form $\mathbb{F}_2[x]/(f(x))$ where $f(x)$ is a monic irreducible polynomial of degree $n$, but again, there are several such polynomials. An attempt to make a canonical choice of polynomial is to take the ‘first’ suitable one with respect to some natural ordering on the polynomials. This leads to the so called Conway polynomials.

Conway polynomials for the prime $2$ have only been determined up to degree 400-something, so in the increasing sequence above we would already be stuck at the sixth term $\mathbb{F}_{2^{6!}}$…

So, what Alain Connes sets as a problem is to find another, more canonical, description of $\overline{\mathbb{F}}_2$. The problem is not without real-life interest as most finite fields appearing in cryptography or coding theory are subfields of $\overline{\mathbb{F}}_2$.

(My guess is that Alain originally wanted to talk about the action of the Galois group on the roots of unity, which would be the corresponding problem over the field with one element and would explain the title of the talk, but decided against it. If anyone knows what ‘coupling-problem’ he is referring to, please drop a comment.)

Surely, Connes is aware of the fact that there exists a nice canonical recursive construction of $\overline{\mathbb{F}}_2$ due to John Conway, using Georg Cantor’s ordinal numbers.

In fact, in chapter 6 of his book On Numbers And Games, John Conway proves that the symmetric version of his recursive definition of addition and multiplcation on the surreal numbers make the class $\mathbf{On}$ of all Cantor’s ordinal numbers into an algebraically closed Field of characteristic two : $\mathbf{On}_2$ (pronounced ‘Onto’), and, in particular, he identifies a subfield

$\overline{\mathbb{F}}_2 \simeq [ \omega^{\omega^{\omega}} ]$

with the algebraic closure of $\mathbb{F}_2$. What makes all of this somewhat confusing is that Cantor had already defined a (badly behaving) addition, multiplication and exponentiation on ordinal numbers. To distinguish between the Cantor/Conway arithmetics, Conway (and later Lenstra) adopt the convention that any expression between square brackets refers to Cantor-arithmetic and un-squared ones to Conway’s. So, in the description of the algebraic closure just given $[ \omega^{\omega^{\omega}} ]$ is the ordinal defined by Cantor-exponentiation, whereas the exotic identity we started out with refers to Conway’s arithmetic on ordinal numbers.

Let’s recall briefly Cantor’s ordinal arithmetic. An ordinal number $\alpha$ is the order-type of a totally ordered set, that is, if there is an order preserving bijection between two totally ordered sets then they have the same ordinal number (or you might view $\alpha$ itself as a totally ordered set, namely the set of all strictly smaller ordinal numbers, so e.g. $0= \emptyset,1= { 0 },2={ 0,1 },\ldots$).

For two ordinals $\alpha$ and $\beta$, the addition $[\alpha + \beta ]$ is the order-type of the totally ordered set $\alpha \sqcup \beta$ (the disjoint union) ordered compatible with the total orders in $\alpha$ and $\beta$ and such that every element of $\beta$ is strictly greater than any element from $\alpha$. Observe that this definition depends on the order of the two factors. For example,$[1 + \omega] = \omega$ as there is an order preserving bijection ${ \tilde{0},0,1,2,\ldots } \rightarrow { 0,1,2,3,\ldots }$ by $\tilde{0} \mapsto 0,n \mapsto n+1$. However, $\omega \not= [\omega + 1]$ as there can be no order preserving bijection ${ 0,1,2,\ldots } \rightarrow { 0,1,2,\ldots,0_{max} }$ as the first set has no maximal element whereas the second one does. So, Cantor’s addition has the bad property that it may be that $[\alpha + \beta] \not= [\beta + \alpha]$.

The Cantor-multiplication $\alpha . \beta$ is the order-type of the product-set $\alpha \times \beta$ ordered via the last differing coordinate. Again, this product has the bad property that it may happen that $[\alpha . \beta] \not= [\beta . \alpha]$ (for example $[2 . \omega ] \not=[ \omega . 2 ]$). Finally, the exponential $\beta^{\alpha}$ is the order type of the set of all maps $f~:~\alpha \rightarrow \beta$ such that $f(a) \not=0$ for only finitely many $a \in \alpha$, and ordered via the last differing function-value.

Cantor’s arithmetic allows normal-forms for ordinal numbers. More precisely, with respect to any ordinal number $\gamma \geq 2$, every ordinal number $\alpha \geq 1$ has a unique expression as

$\alpha = [ \gamma^{\alpha_0}.\eta_0 + \gamma^{\alpha_1}.\eta_1 + \ldots + \gamma^{\alpha_m}.\eta_m]$

for some natural number $m$ and such that $\alpha \geq \alpha_0 > \alpha_1 > \ldots > \alpha_m \geq 0$ and all $1 \leq \eta_i < \gamma$. In particular, taking the special cases $\gamma = 2$ and $\gamma = \omega$, we have the following two canonical forms for any ordinal number $\alpha$

$[ 2^{\alpha_0} + 2^{\alpha_1} + \ldots + 2^{\alpha_m}] = \alpha = [ \omega^{\beta_0}.n_0 + \omega^{\beta_1}.n_1 + \ldots + \omega^{\beta_k}.n_k]$

with $m,k,n_i$ natural numbers and $\alpha \geq \alpha_0 > \alpha_1 > \ldots > \alpha_m \geq 0$ and $\alpha \geq \beta_0 > \beta_1 > \ldots > \beta_k \geq 0$. Both canonical forms will be important when we consider the (better behaved) Conway-arithmetic on $\mathbf{On}_2$, next time.

I couldn’t believe my eyes. I was watching an episode of numb3rs, ‘undercurrents’ to be precise, and there it was, circled in the middle of the blackboard, CEILIDH, together with some of the key-exchange maps around it…

Only, the plot doesn’t involve any tori-crypto… okay, there is an I-Ching-coded-tattoo which turns out to be a telephone number, but that’s all. Still, this couldn’t just be a coincidence. Googling for ‘ceilidh+numbers‘ gives as top hit the pdf-file of an article Alice in NUMB3Rland written by … Alice Silverberg (of the Rubin-Silverberg paper starting tori-cryptography). Alice turns out to be one of the unpaid consultants to the series. The 2-page article gives some insight into how ‘some math’ gets into the script

Typically, Andy emails a draft of the
script to the consultants. The FBI plot
is already in place, and the writers want
mathematics to go with it. The placeholder “math” in the draft is often nonsense or
jargon; the sort of things people with no
mathematical background might find by
Googling, and think was real math. Since
there’s often no mathematics that makes
sense in those parts of the script, the best
the consultants can do is replace jargon
that makes us cringe a lot with jargon that
makes us cringe a little.

From then on, it’s the Telephone Game.
The consultants email Andy our suggestions (“replace ‘our discrete universes’
with ‘our disjoint universes'”; “replace
the nonsensical ‘we’ve tried everything
-a full frequency analysis, a Vignere
deconstruction- we even checked for
a Lucas sequence’ with the slightly less
nonsensical ‘It’s much too short to try
any cryptanalysis on. If it were longer
we could try frequency analyses, or try
to guess what kind of cryptosystem it is
and use a specialized technique. For example, if it were a long enough Vigenere
cipher we could try a Kasiski test or an
index-of-coincidence analysis’). Andy
chooses about a quarter of my sugges-
tions and forwards his interpretation
of them to the writers and producers.
The script gets changed, and then the
actors ad lib something completely dif-
ferent (‘disjointed universes’: cute, but
loses the mathematical allusion; ‘Kasiski
exam’ : I didn’t mean that kind of ‘test’).

She ends her article with :

I have mixed feelings about NUMB3RS. I still have concerns about the violence, the depiction of women, and the pretense
that the math is accurate. However, if NUMB3RS could interest people in the power of mathematics enough for society
to greater value and support mathematics teaching, learning, and research, and
motivate more students to learnthat would be a positive step.

Further, there is a whole blog dedicated to some of the maths featuring in NUMB3RS, the numb3rs blog. And it was the first time I had to take a screenshot of a DVD, something usually off limits to the grab.app, but there is a simple hack to do it…