SAGE UW Seminar

• Thur, Mar 1, 4-5pm: Martin Albrecht in B027:

Algebraic Attacks against Block Ciphers

In recent years a new attack technique against block ciphers has been discovered/proposed involving commutative algebra. I will briefly state the main ideas behind this technique, which often boils down to calculating a reduced lexicographical Gröbner basis for an ideal spanned by an equation system derived from the encryption algorithm.

Also, I will give examples of such attacks using SAGE, give an overview about the state of the art and present my 5-line "algorithm" "Gröber Surfing".

• Fri, Mar 2, 10:30 in B027: Robert Miller -- Title: Opening Graph Automorphisms

Abstract:

Brendan McKay has written what many people agree to be the world's fastest automorphism computation package, "nauty." The package is given a labelled graph G and an ordered partition P, and it outputs the partition stabilizer subgroup of the automorphism group and, optionally, the canonical label C(G,P). If P is the unit partition, this means the whole automorphism group and the canonical label C(G). Canonical labels are in one-to-one correspondence with isomorphism classes.

The package has a restrictive license, which excludes it from use in the open source community. The algorithm is described in McKay's paper, "Practical Graph Isomorphism," and luckily, academic Journals are amongst the most open of sources. The big picture of the algorithm will be explained, and reproductions of a few subroutines will be demonstrated.

Past

• Wed, Feb 28, Padelford 401, 5-6pm: Jim Morrow -- Algorithms for Discrete Electrical Networks

  • ABSTRACT: I will present algorithms for recovery of information about discrete electrical networks. Time permitting, I'll also discuss algorithms for embedding graphs in Riemann surfaces.
• Friday, March 2: TBA
• Friday, March 9: TBA
• Friday, March 16: TBA

Things Martin Albrecht may talk about during his visit:

Hi everybody, 
 
this is a list of stuff I could talk about. I didn't think those through, just 
stuff that came to mind.
 
 * Pyrex/SageX (I know e.g. Robert Miller wants to start hacking Pyrex to 
    speed up the graph stuff)
 * Wrap up of what happened at the MSRI workshop
 * Algebraic attacks on block ciphers and Groebner bases in SAGE 
 * 

Fridays 4-5pm in C401, at least -- probably more frequently!

• Friday, Jan 19 (at 4pm): William Stein -- SAGE 2.0
• Friday, Jan 19 (at 5pm): William Stein -- Tutorial introduction to using SAGE for the Modeling Contest (etc.)

• Friday, Jan 26: Andrey Novoseltsev: PALP

  • PALP is a Package for Analyzing Lattice Polytopes, written by Maximilian Kreuzer and Harald Skarke during their work with reflexive polytopes, that appear in connection with toric varieties, Calabi-Yau manifolds, and string theory. It contains several command line applications written in C, is quite small and fast. Recently is was included into standard distribution of SAGE, together with lattice_polytope.py module that uses some of its functions. I will talk about PALP itself, functions and structure of lattice_polytope.py module, and directions for improvement/development.
• Friday, Feb 2: TBA (I will be gone)
• Friday, Feb 9: TBA (I will be gone)

Talks are all in the communications building, B027, except on Tuesday, Feb 13:

• Monday, Feb 12, 9 A.M.: William Stein -- [http://sage.math.washington.edu/talks/2007-02-12-linalg/sage.pdf Optimized linear algebra in SAGE: What are we going to do???]

• Monday, Feb 12, 4 P.M.: Martin Albrecht -- [http://www.informatik.uni-bremen.de/~malb/binary/20070212-commutative_algebra-UW.pdf Options for fast multivariate polynomial arithmetic in SAGE (CoCoALib, Singular, specialized implementations)]

• Tuesday, Feb 13, 9 A.M.: Josh Kantor -- [http://sage.math.washington.edu/home/jkantor/talks/parallelism.pdf Report about the MSRI workshop on interactive parallel computation]

• Tuesday, Feb 13, 5 P.M.: William Stein -- [http://www.math.washington.edu/~greenber/steinabstract.pdf The arithmetic of elliptic curves (in the number theory seminar -- C401)]

• Wednesday, Feb 14, 9 A.M.: Martin Albrecht -- [http://www.informatik.uni-bremen.de/~malb/binary/20070214-pyrex-uw.pdf Pyrex/SageX]

• Thursday, Feb 15, 9 A.M.: Robert Miller and Emily Kirkman -- Informal Introduction to the Graph Theory Package

• Thursday, Feb 15, 4 P.M.: Robert Bradshaw: The status and plan for 3D graphics in SAGE [attachment:Sage3D.pdf]