Todays webbrowsing led me to John Baez finds in mathematical physics
for week 226, which led
me to snoop around John Baez
homepage, which in turn led me to
stumble across the Geometry of
Computation school and conference
in Marseilles right now.
This, in turn, leads to several different themes for me to discuss.
Cryptographic hashes
In the weeks finds, John Baez comes up to speed with the cryptographic
community on the broken state of SHA-1 and MD-5. Now, this is a drama
that has been developing with quite some speed during the last 1-1½
years. It all began heating up seriously early 2005 when Wang, Yin and
Yu presented a paper detailing a serious attack against SHA-1. Since
then, more and more tangible evidence for the inadvisability of MD-5 and
upcoming problems with SHA-1 have arrived - such as several example
objects with different contents and identical MD-5 hashes: postscript
documents (Letter of Recommendation and Access right granting), X.509
certificates et.c.
The attacks that occur are what is called collision attacks by those
in the trade. They find data [tex]x[/tex] and [tex]y[/tex] such that
[tex]H(x)=H(y)[/tex]. The other serious attack is the preimage attack,
where to a specific hash [tex]y[/tex], a message [tex]x[/tex] is found
such that [tex]H(x)=y[/tex]. Once preimages can be found, it's time to
bail ship quickly. Up until then, it may possibly be enough to pack the
life boats and look toward the horizon for possible rescues or deserted
islands.
Very interesting reads and link sources for this can be found, as with
most things cryptographic, with Bruce
Schneier.
Topology of computation
John Baez talks about some
lectures he gave at the
Geometry of Computation conference in the section of Universal Algebra
and Diagrammatic Reasoning. Reading through what he did and looking over
the conference as such, I realize I would very much have wanted to be
there. They're doing linguistics and algebraic topology together, for
one!
John Baez' talk (well worth to review the slides! Go do it!) goes
through a lot of the themes I'm busying myself with from the vantage
point of computer science and computation theory. He talks about PROPs,
about PROs, about Monads and categorical monoids, about diagrams and
algebraic theories et.c. Most of it very interesting, and rather close
to my own work. If I now can work out some good method to display that
the Koszul resolutions of PROPs are the same kind of resolutions that
Baez uses to get simplicial objects representing computations, I might
just close in to something that may give a good explanation as to why
the things I like are relevant.
I will bring my post on Operads and PROPs at some point in the future.
As will I bring my expose over Koszulness. But not today.
Geometry of roots
The third eye-catcher I found was an absolutely gorgeous
picture of all roots of
polynomials of degree at most 5 and with integer coefficients in
[tex][-4,4][/tex]. It makes me want to build more pictures. Now, if I
may. Dunno if this is what I -should- be spending the processor cycles
of my workplace on, but damn, they are gorgeous!
I wonder how hard it would be to hack a Pari/GP script that spews out
coordinates and colour tags for this with coefficients in
[tex][-5,5][/tex] in a format amenable to producing pretty graphs. Some
chosen thoughts awake with the comments from John Baez - among other
things, he states that
Odlyzko and Poonen proved some interesting things about the set of
all roots of all polynomials with coefficients 0 or 1. If we define
a fancier Christensen set [tex]C_{d,p,q}[/tex] to be the set of
roots of all polynomials of degree [tex]d[/tex] with coefficients
ranging from [tex]p[/tex] to [tex]q[/tex], Odlyzko and Poonen are
studying [tex]C_{d,0,1}[/tex] in the limit [tex]d\to\infty[/tex].
They mention some known results and prove some new ones: this set is
contained in the half-plane [tex]Re(z) < 3/2[/tex] and contained in
the annulus [tex]1/\phi < |z| < \phi[/tex] where
[tex]\phi[/tex] is the golden ratio [tex](\sqrt5 + 1)/2[/tex]. In
fact they trap it, not just between these circles, but between two
subtler curves. They also show that the closure of this set is path
connected but not simply connected.
Now, if the set isn't simply connected, then I'm immediately growing
interested in the homology and homotopy of the set.