Modulo Errors

On Friday I gave a geometry club seminar, speaking about some of the computational aspects of discrete-logarithm cryptography in general and as implemented for elliptic curves. My notes supplement rather than completely describe the talk, being heavier on the formalities and lighter on the narrative.

The topics covered are: Diffie-Hellman and one-way functions for key exchange; the generic Discrete Logarithm Problem and BSGS algorithm; scalar multiplication- addition chains, fast exponentiation, m-ary methods and windowing; group law implementations, Side-channel attacks and the Edwards form.

I’ve discussed several of these ideas elsewhere on this blog, as well as the cryptanalysis ideas I mentioned on the day but which are not in the notes. I also refered to a recent real-world example of a side-channel attack; see this story from The Register for details.

Today I gave the first of this year’s postgraduate colloquia series, The Mathematics of Being Nice- cooperation in the Prisoner’s Dilemma. You can grab the slideshow as pdf here; since the potential audience was quite broad (and I’m no expert) I think it’s fairly light technically, and thus hopefully more accessible than many of my posts here. It’s essentially the talk version of my article for iSquared, so you should invest in a copy of that if you want something that’s more fleshed out!

Tomorrow I give my first year presentation, which determines whether I’m allowed to continue my studies. At 20-30 minutes, it’s a rather condensed version of my recent geometry club talk on the point counting problem, although this time I’m skipping more quickly through the fundamentals so that I can discuss some of the algorithms in depth, and taking a (hopefully) clearer route.

Both the report itself and the OHP slides version are available (pdf). Content covered: hyperelliptic curves, points, divisors, mumford polynomials and the Picard group/Jacobian; the discrete logarithm problem; explicit group law computation; characteristic polynomial of Frobenius and Weil theorems/interval; group-theoretic approaches; Schoof’s algorithm, SEA in genus 1, genus 2 hybrid algorithms.

Today I spoke at the Geometry Club about the use of hyperelliptic curves in public key cryptography. You can find my slides here, although they were supplemented by some boardwork that you’ll have to figure out from my other postings!

Despite my usual resistance to applied maths, yesterday’s BICS seminar sounded worthwhile, and turned out to be very good- Keith Briggs of BT gave a talk entitled Some practical experiences of hard graph problems. Graph Theory isn’t part of our syllabus, which seems a shame, as the concepts are simple- colouring, cliques etc. - but the questions difficult.

Much of the talk discussed the validity of results on infinite graphs when applied to smaller (and hence computationally feasible) ones: in particular, obtaining good bounds on clique and chromatic numbers. Towards the end, the reduction of graph problems to the satisfiability problem in propositional logic was mentioned. Obviously, the possibility of such reductions is a defining characteristic of NP-hard problems (and one I’ve recently been studying), but it’s good to see that this is of practical merit rather than simply theoretical interest.

I managed to arrange a talk by Nina Snaith for the final event by the undergraduate maths club I helped set up this year. As at Durham, she spoke on her work connecting quantum chaos to the moments of the riemann zeta function, via random matrix theory. Turnout was good, including some postgrads and staff, and the advantage of hearing the talk here is that I benefit from any feedback or insights they have.

To calculate the moments requires knowledge of a particularly elusive coefficient g_k, about which very little is known: g₀ is trivially 1, Hardy and Littlewood established that g₁=1 in the early part of the 20th century, Ingham proved that g₂=2 in 1926. No progress was made until 1995, when Conrey and Ghosh conjectured that g₃ was, of all things, 42. At a conference in Vienna, Conrey and Gonek planned to present a conjecture for g₄; yet the random matrix theorists had a conjecture for all values of k. Following some frantic checking at a blackboard, it was confirmed that the two conjectures agreed for g₄=24024: and thus that quantum physics really could offer predictions about number theory!

One of my lecturers plugged the coefficients 1,1,2,42,24024 into the OEIS, and just one result comes up, sequence A039622. Curiously, this is about Young diagrams, which are linked to irreducible representations of the symmetric group. Young Tableau themselves describe a fairly elegant number theory puzzle. I’ve been studying representation theory this semester, and I’m always amazed by how different strands of mathematics can pull together like this- from quantum theory to distribution of primes to symmetry, somehow they’re all woven together.

For an overview of the current status of work on the Riemann Hypothesis, including Random Matrix Theory, see this article by Conrey. Marcus Du Sautoy’s the music of the primes also mentions Nina’s work, and Riemann’s own study of problems in Physics alongside the zeta function.

So, I attended my first mathematics conference last week; two days of pure mathematics talks to lure us into postgraduate study. There are very few ‘pure’ topics I wouldn’t enjoy a lecture on, and I’ve been attending my own university’s staff/postgrad colloquia series this semester simply out of mathematical curiosity and enthusiasm. But beyond this entertainment value, the Durham lectures helped confirm/deny some opinions on potential research areas, so the event was certainly worthwhile.

Michael Drischel (Nottingham) gave the first talk, on Sums of Squares, which you can find online, so I won’t discuss the content too much.

Bill Jackson (Queen Mary London) presented a talk on Rigidity of Graphs concerning combinatorics and graph theory. The first section was presented using the geometry package Cinderella with which I was working for my summer research, demonstrating its many applications. This isn’t a field I’ve studied at all, but the ideas are both accessible and interesting so the talk was one of my favourites. There were even some connections to organic chemistry, which I haven’t thought about for a long time!

Patrick Dorey (Durham) gave a talk entitled Surprises in Quantum Mechanics; sadly I doubt I can ever get to grips with this topic (I can only remember abandoning two books partly read, and both were on Quantum Physics). However (ignoring a talk on funding) the next talk managed to overcome even my general dislike of Physics- Nina Snaith (Bristol)’s talk Every moment brings a treasure: how physicists came to the rescue of number theory. This was one of the more entertaining presentations anyway, but the central result was genuinely intriguing- how random matrix theory, a topic developed in the context of mathematical physics, was able to back up conjectures related to the Riemann zeta function arrived at by traditional number theoretic approaches. The method has turned out to have applications in other areas, and even features as a plot device in the film Proof!

The first day closed with a traditional talk-and-chalk on Geometry and integrability by David Calderbank. Due to a quirk of the MMath structure, I wasn’t allowed to take our differential geometry course. So this was a topic I knew very little about; the talk itself was interesting but I don’t think the field holds much appeal for me. Playing with surfaces is fun, but I prefer my analysis to be more topological rather than heavily connected to calculus.

Some of the ideas of the previous talk were picked up in the first of day two; Michael Singer (Edinburgh) giving an outline of a popular example of an integrable systems in a talk entitled The geometry of nonlinear waves. I’m hoping to track down the Maple worksheet for this one; you really have to see the graphs (or perform experiments with canals!) to appreciate what’s going on.

The most influential talk for me was John Cremona (Nottingham)’s Explicit methods in Number Theory. This was more accurately subtitled Rational points on curves and has cemented my interest in Algebraic Number Theory. For some time I’ve been deliberating between algebraic geometry and algebraic number theory; hindered by our lack of a number theory course at Bath! Based on this talk (and fortunate discussions with John at breakfast) it seems that the aspects of the algebraic geometry course I particularly liked more naturally fall within the remit of number theory; as do the bits of computer algebra that I enjoyed.

Norbert Peyerimhoff (Durham) spoke on averaging and equidistribution problems in geometry; I think this was another talk-and-chalk but I didn’t make notes because the content didn’t really appeal (didn’t help that it got very difficult very quickly!). Similarly Cobordism and groups of formal power series by Neil Strickland (Sheffield) confirmed that algebraic topology, whilst utterly fascinating, is really really difficult. Maple users can find the talk itself at this address, a non-interactive pdf version is also available if you can’t read Maple10 (it seems that, with Maple9.5, I can’t).

The final talk, given by Farid Tari (Durham) Singularities and the imagination offered more diffgeo, and an opportunity for me to demonstrate my complete lack of spatial awareness during the ‘practical’ component where we attempted to build some surface out of a piece of paper! Again, interesting as a talk but not as a career (although Farid was a very good speaker and well suited to holding our attention at the end of a demanding two days).